链表¶

link : 代码随想录链表部分

1. 链表介绍¶

1.1 链表的分类¶

单链表

链表：链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

图示：

双链表

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表既可以向前查询也可以向后查询。

图示：

循环链表

循环链表，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

1.2 链表的存储方式¶

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

即数组在内存中是连续分布的，链表在内存中不是连续分布的

这个链表起始节点为2，终止节点为7，各个节点分布在内存的不同地址空间上，通过指针串联在一起。

1.3 链表的实现（代码实现）¶

public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

一定要自己定义构造函数, 从而便于在初始化的时候为数据域赋值

1.4 链表的操作¶

删除节点

删除节点 D ：

将C节点的next指针指向E节点就可以了

添加节点

添加节点 F ：

链表的增添和删除都是O(1)操作，也不会影响到其他节点。但是如果删除最后一个节点，就需要从头开始查找，复杂度为 $O(n)$

1.5 性能分析¶

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

2. 移除链表元素¶

link : LeetCode 203

思考：

以链表 1 4 2 4 来举例，移除元素4：

特殊情况：移除头节点

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

移除头节点的两种方式：

直接使用原来的链表来进行删除操作。
设置一个虚拟头结点在进行删除操作

方法一：直接使用原来的链表来进行删除操作。(将头结点向后移动一位，这样就从链表中移除了一个头结点)

这种情况下，将移除头节点作为一种特殊的情况，单独写一段代码来处理

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        // 直接在原链表进行操作

        // 判断头节点是否满足要求

        // 必须使用while, 从而保证得到的 链表 头节点不满足要求

        // 比如 1 1 1 1 2, val=1 的情况

        while(head != null && head.val == val){

            head = head.next;

        }

        // 判断非头节点

        // 非头节点的删除是通过前一个节点来完成

        ListNode newNode = head;

        // 需要判断 newNode是否为空

        // 比如 1 1 1 1 1, val = 1, 那么 newNode=null

        while(newNode != null && newNode.next != null){

            if (newNode.next.val == val){

                newNode.next = newNode.next.next;

            }else{

                newNode = newNode.next;

            }

        }
        return head;

    }

}

方法二：设置一个虚拟头结点在进行删除操作 (这样原链表的所有节点就都可以按照统一的方式进行移除了)

最后在题目中，return 头结点的时候，别忘了 return virtualHead.next;

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode removeElements(ListNode head, int val) {

        // 设置一个虚拟节点, 从而使得删除头节点和删除非头节点都是通过前面的节点实现

        ListNode virtualHead = new ListNode(-1, head);

        ListNode newNode = virtualHead;

        while(newNode.next != null){

            if (newNode.next.val == val)

                newNode.next = newNode.next.next;

            else newNode = newNode.next;

        }
        return virtualHead.next;
    }

}

3. 设计链表¶

link : LeetCode 707

思考：

这道题目设计链表的五个接口：

获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点

链表操作的两种方式： - 直接使用原来的链表进行操作 - 设置一个虚拟头节点进行操作

采用设置一个虚拟头节点的方法：

// 定义链表节点类

class ListNode{

    int val;

    ListNode next;



    public ListNode(){}



    public ListNode(int val){

        this.val = val;

    }



}




class MyLinkedList {



    // 链表的虚拟头节点

    ListNode virtualHead;

    // size: 链表的元素个数

    int size;




    // 初始化链表

    // 此处是初始化一个虚拟的头节点

    public MyLinkedList() {

        this.virtualHead = new ListNode(-1);

        this.size = 0;

    }

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点

    // 因为index是从0开始, 所以index的有效范围为 [0, size-1]

    public int get(int index) {

        if (index >= size || index < 0) return -1;



        ListNode tempNode = virtualHead;

        int res;

        // 因为包含了虚拟节点,所以进行查找的时候需要查找到 第 index+1 个节点

        for (int i=0; i <= index; i++){

            tempNode = tempNode.next;

        }
        res = tempNode.val;



        return res;




    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点

    public void addAtHead(int val) {

        ListNode newHeadNode = new ListNode(val);

        // 因为是在链表的最前面插入一个节点, 所以下一个节点是原链表的头节点

        newHeadNode.next = this.virtualHead.next;

        this.virtualHead.next = newHeadNode;

        // 插入一个节点, 链表的长度加一

        this.size++;

    }

    // 在链表最后面添加一个节点

    public void addAtTail(int val) {

        ListNode newNode = new ListNode(val);

        ListNode tempNode = this.virtualHead;

        while(tempNode.next != null)

            tempNode = tempNode.next;

        tempNode.next = newNode;



        // 链表节点加一

        this.size++;



    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。

    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点

    // 如果index大于链表的长度，则返回空

    // 如果index小于0，则在头部插入节点

    public void addAtIndex(int index, int val) {

        // 在头部插入节点

        if (index <= 0){

            this.addAtHead(val);

        }

        else if(index == size){

            this.addAtTail(val);

        }else if (index > size){

            return;

        }else{



            ListNode newNode = new ListNode(val);

            ListNode tempNode = this.virtualHead;

            // 因为是插入到 链表中下标为index的节点之前, 所以需要找到该节点前面的 节点

            // 而因为链表中有虚拟头节点, 所以相当于需要找到第 index - 1 + 1个节点

            for (int i=0; i<index; i++)

                tempNode = tempNode.next;



            // 找到前面的节点

            newNode.next = tempNode.next;

            tempNode.next = newNode;

            size++;
        }

    }

     // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的

    public void deleteAtIndex(int index) {

        if (index >= 0 && index < size){

            ListNode tempNode = this.virtualHead;

            // 找到下标为 index 的前面的节点

            for (int i=0; i<index; i++)

                tempNode = tempNode.next;



            // 进行删除

            tempNode.next = tempNode.next.next;



            size--;



        }else return;

    }

}

4. 反转链表¶

link: LeetCode 206

思考：

只需要改变链表的 next 指针的指向，就可以直接将链表反转，从而不用定义一个新的链表

双指针法：

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

之后需要pre 和 cur 都向前走一位

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode reverseList(ListNode head) {

        // 使用双指针, 一个pre, 一个curNode, 一个指向当前节点之前的节点, 一个指向当前节点



        ListNode pre = null;

        // 当前的节点

        // 需要当前节点遍历整个链表

        ListNode curNode = head;

        // 当前节点的下一个节点

        ListNode tempNode;



        while(curNode != null){

            tempNode = curNode.next;

            curNode.next = pre; // 改变当前节点的指向



            // 更新 pre 和 curNode, 都向前走一位

            pre = curNode;

            curNode = tempNode;

        }

        // 遍历结束后, pre正好指向最后一个节点, curNode = null

        // 因为改变了指针的指向, 所以最后的节点变成了头节点

        return pre;





    }

}

5. 两两交换链表中的节点¶

link: LeetCode 24

思考：

因为需要进行节点交换，而不是单纯更改节点内的值，因此需要改变节点的指针

图示:

交换过程：

初始的时候，cur指针指向虚拟的头节点（其实可以将cur看成虚拟头节点）

对节点的操作，需要前面的节点才能找到，因此为了保证对头节点的操作逻辑和与其他节点相同，涉及到链表的节点操作都用虚拟头节点

tmp1 = cur.next
tmp2 = cur.next.next.next

cur.next = cur.next.next // 指向 cur->2
cur.next.next = tmp // 2->1
cur.next.next.next = tmp2 // 1->3

// 更新cur, 向前移动两位

cur = cur.next.next // cur指向1号节点

操作之后的链表

即：

代码实现：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode swapPairs(ListNode head) {

        // 使用虚拟头节点

        ListNode virtualNode = new ListNode(-1, head);

        // 定义当前节点, 一开始指向虚拟头节点, 从而保证处理头节点和其他节点采用相同的逻辑

        ListNode curNode = virtualNode;



        // 需要进行交换的是 curNode.next 和 curNode.next.next

        // 因此需要保证两者都不为null

        while (curNode.next != null && curNode.next.next!=null){

            ListNode tmp1 = curNode.next;

            // 要保证链表的连接

            ListNode tmp2 = curNode.next.next.next;



            curNode.next = curNode.next.next; // cur->2

            curNode.next.next = tmp1; // 2->1

            curNode.next.next.next = tmp2; // 1->3



            // 交换之后, cur 向前移动两位, 移动到 下一组需要交换的两个节点的前面一个节点

            curNode = curNode.next.next;

        }



        return virtualNode.next;





    }

}

6. 删除链表的倒数第N个节点¶

link : LeetCode 19

思考： 要删除倒数第N个节点, 那么必须找到该节点前面的节点

使用双指针：双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

思路：

为了保证操作头节点的逻辑和操作其他节点相同，使用虚拟头节点

定义fast指针和slow指针，初始值为虚拟头结点，如图：
fast首先走n + 1步，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：(移动n步也可以, 代码实现是按照移动n步)

fast和slow同时移动，直到fast指向末尾，如题：
删除slow指向的下一个节点，如图：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 定义一个虚拟头节点, 从而保证处理头节点的逻辑和处理其他节点相同

        ListNode virtualNode = new ListNode(-1, head);

        // 使用双指针, 先让fastNode向前移动n步, 然后两者一块移动

        // 当 fast指针 指向链表最后一个元素, slow指针指向目标节点的前一个节点

        ListNode slowNode = virtualNode;

        ListNode fastNode = virtualNode;

        for (int i=0; i<n; i++){

            fastNode = fastNode.next;

        }



        // 两者同时移动

        // 当fastNode指向最后的一个元素跳出循环

        while(fastNode.next != null){

            slowNode = slowNode.next;

            fastNode = fastNode.next;

        }



        // 删除目标元素

        slowNode.next = slowNode.next.next;



        return virtualNode.next;



    }

}

7. 链表相交¶

link: LeetCode 160

思考：

题目即为求两个链表交点的节点的指针（即 c1），但是交点不是数值相等, 而是指针相等, 比如下面的图是：

很明显，相交的节点是 “8”，而不是 “1”

思路：

首先求出两个链表的长度，然后求出两个链表的长度的差值，然后将指向长度比较长的链表的指针先移动

比如下面图示：

如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

从而比较 curA和curB是否相等, 如果不相等的话，继续同时向后移动

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode curA = headA;

        ListNode curB = headB;



        int lenA = 0, lenB = 0;

        // 求出两个链表的长度

        while(curA != null){

            curA = curA.next;

            lenA++;

        }

        while(curB != null){

            curB = curB.next;

            lenB++;

        }



        curA = headA;

        curB = headB;



        // 保证 A 链表是长度比较长的链表

        // 如果不是则交换, 从而保证下面的逻辑通用

        if (lenB > lenA){

            int temp = lenA;

            lenA = lenB;

            lenB = temp;



            ListNode tempNode = curA;

            curA = curB;

            curB = tempNode;

        }





        // 下面首先长度比较长的链表先移动两者的差值

        int gap = lenA - lenB;

        while(gap-- > 0){

            curA = curA.next;

        }



        // 判断curA和curB是否相等

        while(curA != null){

            if (curA == curB) return curA;



            curA = curA.next;

            curB = curB.next;



        }



        return null;







    }

}

8. 环形链表 (重点看)¶

link: LeetCode 142

题目描述：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

思考：

link : 代码随想录环形链表

video:

考察两方面的内容： 1. 判断链表是否有环（快慢双指针） 2. 如果有环，如何寻找环的入口处

判断链表是否有环：

使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。

fast 必须是移动两个节点，slow 必须是移动一个节点，这样快指针相当于以每次多移动一个节点的速度追赶慢指针，如果有环，则必定能够追赶上。如果fast每次移动三个节点，slow每次移动一个节点，这样快指针相当于以每次多移动两个节点的速度追赶慢指针，那么有可能会跳过慢指针

fast 和 slow的移动图示：

如果链表中有环，如何寻找环的入口：

假设从头节点到环形入口节点的节点数是 $x$ , 环形入口节点到 fast与slow相遇节点的节点书为 $y$, 从相遇节点啊到环形入口节点的节点数为 $z$

fast与slow 相遇的时候, slow 走过的节点数为 $x+y$ , fast走过的节点数为 $x + n(y + z) + y$

slow 必定是在进入环中第一圈的时候被fast遇到 fast 必定是在环中走了至少一圈，然后遇到了slow， $n$ 表示fast在环中走的圈数

因为fast每一步走两个节点, slow每一步走一个节点，所以相遇的时候根据走过的路径距离形成一个等式： $$ 2(x + y) = x + n(y + z) + y $$ 左右两边同时消去 $x + y$, 并且把 $x$ 单独放在左边： $$ x = n(y + z) - y $$

此时看不出什么等量关系，从 $n(y+z)$ 中提取出来一个 $y + z$ $$ x = (n-1)(y+z) + z $$

其中 $y+z$ 是环形中的节点数目，如果 $n=1$, 即fast 在环形中走一圈后, 与 slow 相遇, 那么 $x = z$

即：从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。（另一个等量关系）

当然，也有可以 fast 在环形中走了若干圈(即 n!=1), 与 slow 相遇, 但是即使是这样, 从头节点出发一个指针index1，从相遇节点也出发一个指针index2，这两个指针每次只走一个节点，即使 index2 在环中走了若干圈，但是最后仍然会和 index1 相遇

index1 = head;
while (index1 != index2){
    index1 = index1.next
    index2 = index2.next
    size++;
}

// 循环必定会打破, 打破循环的时候 index1=index2 就是环的入口

代码实现：

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode detectCycle(ListNode head) {

        // 1. 使用快慢指针找到相遇的地方

        ListNode fast = head;

        ListNode slow = head;

        while(fast != null && fast.next != null){

            fast = fast.next.next;

            slow = slow.next;



            if (fast == slow){

                // 2. 寻找环的入口

                ListNode index1 = head;

                ListNode index2 = slow;



                while(index1 != index2){

                    index1 = index1.next;

                    index2 = index2.next;

                }

                return index1;

            }

        }



        return null;







    }

}