[Vssue]0142.环形链表II.md

[youngyangyang04]

https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

[JiangXiuXiang]

我不理解这句话“ fast相对于slow是一次移动一个节点”，怎么理解呢？

[WEITAOLEE]

Better to refer to me note of this puzzle.

[X-Moodles]

@JiangXiuXiang

我不理解这句话“ fast相对于slow是一次移动一个节点”，怎么理解呢？

每次移动fast指针都比slow指针多移动一个节点，抽象成竞速的相对位移应该不难理解

[hoboxr]

说一下自己对于相遇时slow指针一定在第一次的圈内想法（slow的 步数 是 x+y 而不是 x + 若干环的长度 + y ）： 进了环之后就想成追及问题，fast速度为1，slow速度为0（原地不动），不管刚入环fast在slow前还是后，最后肯定是在一圈内的时间和slow相遇，最后这个追及时间乘以slow的真实速度1，长度小于一个圈的长度，所以结果还是在第一轮的圈内

[Du1in9]

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 1. not fast != null && slow != null
        // 2. not fast.next != null && fast != null
        while (fast != null && fast.next != null) {     
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { // 有环
                ListNode index1 = head;
                ListNode index2 = fast;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null; // 无环, 或空链表
    }
}

[Ding-Jiaxiong]

打卡

package LinkedList.LeetCode142;

/**
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * <p>
 * 思路：快慢双指针
 *
 * @author Ding Jiaxiong
 */

public class Main {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static ListNode detectCycle(ListNode head) {

        ListNode slow = head; //
        ListNode fast = head;

        while (true) {

            if (fast == null || fast.next == null) return null;  // 只有一个节点不会有环

            fast = fast.next.next;  // 快指针一次走两步
            slow = slow.next;  // 慢指针一次走一步

            if (fast == slow) {  // 走到重合
                break; // 跳出
            }
        }

        fast = head;  // 快指针重新回到头
        while (fast != slow) {  // 同样速度再次出发

            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }

    public static void main(String[] args) {

        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;

        System.out.println(detectCycle(node1).val);

    }
}

[YaQia]

这个思路真的很棒，我想补充一些东西：这个循环链表里，慢指针只要开始进入环了，那就绝对不会需要走超过一个环快指针就能赶上它。而之所以直观上会觉得快指针可能跳过慢指针有两种可能：1. 把以同一起点开始出发的快慢指针当成了证明快指针可以跳过慢指针的例子（但这实际上需要相同起点的情况下慢指针才可能被快指针跳过）；2. 把快指针想象成运动的，却忘了把慢指针也同时想象成动起来的状态了（导致在快慢指针只差一个节点的间隔时，考虑一次性跳两个节点的快指针看似会“越过”慢指针原来的位置，但实际上慢指针也往后移动了一个节点，所以它俩是能回到同一个节点上的）。

[Bryan-CR7]

打卡：龟兔赛跑判环法

[Fx386483710]

对我来说这么理解更好：因为 x = n(y+z) -y，而此时index2就在环形口后y的位置，它要第n次走到环形口就需要走n(y+z) -y步，也就是x步。所以不论n取多少一定相遇在环形口。

[BAI-demon]

其实可以直接假设最坏的情况，slow 入环的时候，fast 刚好在它前一位的地方。 此时 slow 和 fast 相遇刚好就是 slow 差一步走到环入口的地方（即没走完一个环），所以其他情况下，slow 也不可能走完一个环。

[white-bubbleee]

为什么第一次在环中相遇，slow的 步数 是 x+y 而不是 x + 若干环的长度 + y 呢？换句话说slow一定是在第一次绕环内被fast追上。 考虑slow第一次到达环口，此时fast一定已经在环中，假设环长N，那么fast和slow的距离L一定小于等于N，而fast和slow的速度差是1，这意味着slow第一次到达环口之后，slow再走L个节点(fast会走2L节点，刚好fast比slow多走L个节点)，fast就会追上slow，而L一定小于等于N，所以slow在一次绕环没结束(或者刚好结束)就会被fast追上。