链表专题

链表类型

单链表

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

双链表

每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

循环链表

循环链表，顾名思义，就是链表首尾相连。可以用来解决约瑟夫环问题。

链表的存储方式

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

链表的操作

删除节点

删除节点，找到目标节点及其前一个节点，将前一个节点的指针域指向目标节点的下一个节点

==D节点不是依然存留在内存里么？只不过是没有在这个链表里而已==❓

Java有自己的内存回收机制，这个内存空间没有具体指向会自己回收，不用手动释放

删除节点有特殊性，因为单链表的特殊性，只能指向下一个节点，如果删除的是头结点又该怎么办呢❓

这里就涉及如下链表操作的两种方式：

直接使用原来的链表来进行删除操作。

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

这种方法在单链表中移除头结点和移除其他节点的操作方式不统一

设置一个虚拟头结点在进行删除操作。==（推荐）==
设置一个虚拟头结点，其中不需要放任何数据，作用就是作为真正意义上的head节点，只用于指向链表中的第一个节点，这样删除节点的方法就统一了

添加节点

找到要插入位置的前一个节点(用a表示)，将目标节点的指针域指向a节点指向的下一个节点，a节点的指针域指向目标节点。

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

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

对于单链表，无所谓删除还是添加，如果我们用一个指针表示遍历的话(cur)，那么一定保持cur.next是我们要操作的对象的中心思想，因为操作时都需要前一个节点来操作。

操作时，主要考虑边界

Java手写链表推荐写法

java

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;
    }

专题题目

203.移除链表元素

题目
给你一个链表的头节点head和一个整数val，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点。
示例 1：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2：输入：head = [], val = 1 输出：[]
示例 3：输入：head = [7,7,7,7], val = 7 输出：[]
思路
可以用上面写的虚拟头结点或者直接写

我的代码(可以改进，只需要一个cur节点从newHead开始，待删除的节点是cur.next即可，这样不需要引入下面的pos，下面的pos就可以改成pre.next了)

java

/**
 * 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) {
        if(head == null){
            return head;
        }
        // 建一个虚拟头结点
        ListNode newHead = new ListNode(-1,head);
        // 建一个指针节点,并记录前一个节点
        ListNode pre = newHead;
        ListNode pos = head;
        while(pos != null){
            if(pos.val != val){
                pre = pos;
            }else{
                // 找到要删除的节点了
                pre.next = pos.next;
            }
            pos = pos.next;
        }
        return newHead.next;
    }
}

官方推荐

java

/**
 * 添加虚节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}
/**
 * 不添加虚拟节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为null，提前退出
    if (head == null) {
        return head;
    }
    // 已确定当前head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}
/**
 * 不添加虚拟节点and pre Node方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val){
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null){
        while(curr.next!=null && curr.next.val == val){
            curr.next = curr.next.next;
        }
        curr = curr.next;
    }
    return head;
}

707.设计链表【中等】

题目
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
思路
主要还是理解链表的操作，有一点理解就是，本题的下标index是从0开始，index是0也就是返回原本的头结点，这样也就找到了index和size之间的关系，即0 <= index <= size - 1才是合法的，size表示的是链表中有效元素的多少，有效是从1开始的，下标是从0开始的

我的代码（单链表）

java

//单链表
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}
class MyLinkedList {
    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head;

    //初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
    public int get(int index) {
        //如果index非法，返回-1
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode currentNode = head;
        //包含一个虚拟头节点，所以查找第 index+1 个节点
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }

    //在链表最前面插入一个节点，等价于在第0个元素前添加
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    //在链表的最后插入一个节点，等价于在(末尾+1,下标也即size)个元素前添加
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        size++;
        //找到要插入节点的前驱
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        if (index == 0) {
            head = head.next;
	    return;
        }
        ListNode pred = head;
        for (int i = 0; i < index ; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

官方推荐（单链表）

java

class MyLinkedList {
    int size;
    ListNode head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i <= index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        index = Math.max(0, index);
        size++;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

class ListNode {
    int val;
    ListNode next;

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

作者：力扣官方题解
链接：https://leetcode.cn/problems/design-linked-list/solutions/1840997/she-ji-lian-biao-by-leetcode-solution-abix/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

206.翻转链表

题目
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示:
并没有添加或者删除节点，仅仅是改变next指针的方向。
那么接下来看一看是如何反转的呢？
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。为什么要保存一下这个节点呢，==因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了==。接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点

我的代码

java

/**
 * 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) {
        // 用pos指向当前，用pre指其前一个
        ListNode pos = head;
        ListNode pre = null;
        ListNode temp = null;
        while(pos != null){
            temp = pos.next;
            pos.next = pre;
            pre = pos;
            pos = temp;
        }
        return pre;
    }
}

官方推荐

java

//迭代
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/reverse-linked-list/solutions/551596/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    
// 递归
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/reverse-linked-list/solutions/551596/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

关于本题用递归的说明:

本题中递归方法和双指针方法是一样的，思路完全一样，但是我们要做的就是把循环的办法改成递归的办法，写的时候可以看着循环的办法去写递归

下面是自己写的递归：

java

class Solution{
	public ListNode reverseList(ListNode head){
        // 只需要调用递归方法，重要的就是参数的初始化，我们在模拟反转的时候，就是让cur指向一个节点，而pre指向它的前一个节点
        // 那么从head出发的话，cur->head,而pre->null
        ListNode cur = head;
        ListNode pre = null;
        ListNode temp = null;
        return reverse(cur,pre);
    }
    
    // 循环时我们着重看中的就是cur和pre，因此递归时重要的也是这两个参数
    public ListNode reverse(ListNode cur, ListNode pre){
        // 既然是递归，就要想着终止条件，当递归到什么程度就应该返回了，这其实和循环一样
        // 最终我们的做法就是pre指向了操作后的头结点，这个时候cur==null
        if(cur == null){
			return pre;
        }
        // 利用temp先把cur.next存储起来，以便于作为递归的参数
        ListNode temp = cur.next;
        // 这里是反转操作
        cur.next = pre;
        // 进入下次递归，这里就是要把新的参数传递给下次递归,这个时候我们就要把最新的cur和pre传入
        // temp指向最新的cur，而这个时候的cur正是pre
        return reverse(temp, cur);
    }
}

24.两两交换链表中的节点【中等】

题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路
建议使用虚拟头结点,此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序
操作之后
直观来看

我的代码

java

/**
 * 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 newNode = new ListNode(-1, head);
        ListNode cur = newNode;
        ListNode temp1 = null;
        ListNode temp2 = null;
        // 奇数和偶数的结束条件分别是cur.next.next==null和cur.next==null，结束前我们要操作
        // 因此我们要把这两种关系相或 然后取非 !(cur.next.next==null||cur.next==null) ->
        // cur.next.next!=null&&cur.next!=null
        // 但是这里一定要注意，&& 短路与， 顺序问题，我们把cur.next != null写在前面是可以作为另一个条件的前提的
        while (cur.next != null && cur.next.next != null) {
            temp1 = cur.next;
            temp2 = cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = temp1;
            temp1.next = temp2;
            // 牢记每次操作前我们都要找到待操作对象的前一个节点，因此cur下一次要到下一对操作节点的前一个，也就是这一对节点的最后一个
            cur = cur.next.next;
        }
        // 这就是做新节点的好处，即可以操作方便，还可以知道操作完以后真正的头结点是谁
        return newNode.next;
    }
}

官方推荐（递归）
递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。
如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。
用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。
java
```
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/swap-nodes-in-pairs/solutions/444474/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

19.删除链表的倒数第N个节点【中等】

题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：
输入：head = [1], n = 1 输出：[] 示例 3：
输入：head = [1,2], n = 1 输出：[1]
思路
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n+1步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
注意点
- 定义fast指针和slow指针，初始值为虚拟头结点，操作一定要有意识的放在待删除节点的前一个节点，如图：
- fast首先走n + 1步，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
- 删除slow指向的下一个节点，如图：

我的代码

java

/**
 * 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 newHead = new ListNode(-1,head);
        ListNode fastNode = newHead;
        ListNode slowNode = newHead;
        // 先判断n的可行性,让快指针前移动n+1
        while( ((n--) >= 0) && fastNode != null ){
            fastNode = fastNode.next;
        }
        // 快慢指针同时移动，知道快指针达到null，此时慢指针就正好到了倒数第n+1个位置，也就是倒数第n个节点前一个
        while(null != fastNode){
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        // slowNode指向了目标节点的前一个节点
        slowNode.next = slowNode.next.next;
        return newHead.next;
    }
}

官方推荐

可以用栈，因为单链表的特性，每一个节点的next域都是指针意义的，它指向下一个节点，其实也就是==指向了下一段链表==，如果我们一次遍历这个链表入栈，然后*出栈n次*，获取这个出栈的节点，它的next域就是接下来的链表，而栈顶是待删除节点的前向节点，这个时候我们只需要让栈顶的next指向当前出栈元素的next，这样就可以啦

java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solutions/450350/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

面试题 02.07. 链表相交

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

思路
简单来说，就是求两个链表交点节点的指针。这里同学们要注意，交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
否则循环退出返回空指针。
我的代码
这道题我没有写，理解问题有错，其实就是两条链表，然后比较这两条链表中*节点*相同的节点
但是暴力破解，肯定不好，巧就巧在这里的设计

官方推荐

java

/**
 * 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) {
		// p1 指向 A 链表头结点，p2 指向 B 链表头结点
		ListNode p1 = headA, p2 = headB;
		while (p1 != p2) {
			// p1 走一步，如果走到 A 链表末尾，转到 B 链表
			if (p1 == null) p1 = headB;
			else p1 = p1.next;
			// p2 走一步，如果走到 B 链表末尾，转到 A 链表
			if (p2 == null) p2 = headA;
			else p2 = p2.next;
		}
		return p1;
    }
}

###142.环形链表II【中等】

题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
```
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
```
1
2
3
示例 3：
```
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
```
1
2
3
思路
我把我们的思路先写下来，让后一步一步用官方的思路去解决
其实从上图中可以看出，x = z + (n - 1) * (y + z)这个数学关系，x正是从链表的开头到环的起点的距离，这也能反应环起点的位置，这里的n >= 1是必要的条件。不论n = 1还是n > 1都能反映这个环的起点就是在n=1时x = z上，也就是说，n不管取值多少这个入口是不变的
==官方思路==
这道题目，不仅考察对链表的操作，而且还需要一些数学运算。
主要考察两知识点：
- 判断链表是否环
- 如果有环，如何找到这个环的入口
####判断链表是否有环
可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢？首先第一点：**fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。**那么来看一下，**为什么fast指针和slow指针一定会相遇呢？**可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。
会发现最终都是这种情况，如下图：其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。
如果有环，如何找到这个环的入口
接下来的思路和我们说的是一样的，
x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。这个公式说明什么呢？
先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。当 n为1的时候，公式就化解为 x = z，
这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。这时只需要在设置一个指向head的节点，让它和相遇时的slow一起移动相同的距离，当他们指向同一个节点的时候，这时就指向了环的起点。

我的代码

java

/**
 * 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) {
        // 先要判断是否有环,定义一个快指针，一个慢指针，如果两个指针能相遇，说明这个链表是有环的
        // 而且，快指针的速度设置为一次跳2个节点，慢指针是1个节点，他们之间的相对速度就是1个节点
        // 那么如果发生了相遇两者就不会错开，而是会指向同一个结点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 判断是否相遇
            if (fast == slow) {
                // 已经证明有环，而且快指针和慢指针这个时候指向同一节点(相遇)
                // 假设链表从头结点到进入环的起始点之间距离是x
                // 环起始点到相遇点为y，从相遇点再到环起始点是z
                // 数学关系， 如果套圈一次那么x = z，从头结点开始和从相遇点开始走过相同的距离就能指向同一个节点
                // 这个节点就是环的起始点，让慢节点和另一个从头开始的节点同时走就行
                ListNode temp = head;
                while (temp != slow) {
                    temp = temp.next;
                    slow = slow.next;
                }
                return temp;
            }
        }
        return null;
    }
}

官方推荐

哈希表：一个非常直观的思路是：我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/linked-list-cycle-ii/solutions/441131/huan-xing-lian-biao-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

链表总结

学完链表以后，我认为最重要的一点就是 在结合画图的情况下，找到目标节点的前驱节点，这样一来，就不易把被节点绕晕，最重要的就是牢记，操作一定要找目标节点的前驱！！！（当然我觉得我们的题目都偏向单链表）

虚头结点

链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

链表的基本操作

在 707.设计链表中，我们通过设计链表把链表常见的五个操作练习了一遍。这是练习链表基础操作的非常好的一道题目，考察了：

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

可以说把这道题目做了，链表基本操作就OK了，再也不用担心链表增删改查整不明白了。

反转链表

在 206.翻转链表讲解了如何反转链表。反转链表是面试中高频题目，很考察面试者对链表操作的熟练程度。给出了两种反转的方式，迭代法和递归法。

建议大家先学透迭代法，然后再看递归法，因为递归法比较绕，如果迭代还写不明白，递归基本也写不明白了。

可以先通过迭代法，彻底弄清楚链表反转的过程！

删除倒数第N个节点

结合虚拟头结点和双指针法来移除链表倒数第N个节点。很精巧，道理就像是比着尺子在移动节点一样，标准就是N+1，当快指针移动到尾节点指向的null时，慢指针指向的正是倒数第N+1个节点，也即倒数第N个节点的前驱节点，这样我们就可以对第N个节点进行操作。

链表相交

使用双指针来找到两个链表的交点（引用完全相同，即：内存地址完全相同的交点）

环形链表

这道题目可以说是链表的比较难的题目了。但代码却十分简洁，主要在于一些数学证明。

ElasticSearch

MQ

Redis

链表专题

链表类型

单链表

双链表

循环链表

链表的存储方式

链表的操作

删除节点

添加节点

Java手写链表推荐写法

专题题目

203.移除链表元素

707.设计链表【中等】

206.翻转链表

24.两两交换链表中的节点【中等】

19.删除链表的倒数第N个节点【中等】

面试题 02.07. 链表相交

如果有环，如何找到这个环的入口

链表总结

虚头结点

链表的基本操作

反转链表

删除倒数第N个节点

链表相交

环形链表

链表专题 ​

链表类型 ​

单链表 ​

双链表 ​

循环链表 ​

链表的存储方式 ​

链表的操作 ​

删除节点 ​

添加节点 ​

Java手写链表推荐写法 ​

专题题目 ​

203.移除链表元素 ​

707.设计链表【中等】 ​

206.翻转链表 ​

24.两两交换链表中的节点【中等】 ​

19.删除链表的倒数第N个节点【中等】 ​

面试题 02.07. 链表相交 ​

如果有环，如何找到这个环的入口 ​

链表总结 ​

虚头结点 ​

链表的基本操作 ​

反转链表 ​

删除倒数第N个节点 ​

链表相交 ​

环形链表 ​

链表专题

链表类型

单链表

双链表

循环链表

链表的存储方式

链表的操作

删除节点

添加节点

Java手写链表推荐写法

专题题目

203.移除链表元素

707.设计链表【中等】

206.翻转链表

24.两两交换链表中的节点【中等】

19.删除链表的倒数第N个节点【中等】

面试题 02.07. 链表相交

如果有环，如何找到这个环的入口

链表总结

虚头结点

链表的基本操作

反转链表

删除倒数第N个节点

链表相交

环形链表