LeetCode.142.Linked List Cycle II 有环链表的环起点

题目描述

142 Linked List Cycle II
https://leetcode-cn.com/problems/linked-list-cycle-ii/
https://leetcode.com/problems/linked-list-cycle-ii/description/

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note:
Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

---

相似题目

Floyd判圈算法/龟兔赛跑算法

有环单链表的环长、环起点和链表长
LeetCode.141.Linked List Cycle 判断链表是否有环
LeetCode.142.Linked List Cycle II 有环链表的环起点

判圈算法的其他应用
LeetCode.287.Find the Duplicate Number 数组中重复的数
LeetCode.202.Happy Number 快乐数

---

解题过程

做完141 Linked List Cycle题，看到相关题目中有这道题，想着顺手一起做了。
但是还是把问题想简单了，我一直认为，快慢指针首次相遇时肯定是快指针刚好绕环一周而慢指针第一次进入环内的时候，但其实不是，首次相遇时快指针可能已经绕环不止一周了，设想链表很长而环很小，则快指针需要在环内绕好多圈来等慢指针。
但是否首次相遇时慢指针肯定还没绕环一周呢？我觉得是肯定的，这样想，慢指针入环时，快指针肯定已经在环内绕圈等着他了，不管此时快指针在慢指针前面还是后面，由于快指针速度是慢指针的2倍，肯定还没等慢指针绕环一周就已经追上它了。

推导一下：
设起点到环入口的长度为s，环入口到相遇点的距离为t，则相遇时慢指针走的距离为s+t，快指针走的距离为s+t+n×r，其中r是环的长度，并且快指针速度是慢指针的2倍从而得到2×(s+t)=s+t+n×r，两边都减去(s+t)得s+t=n×r，即s=n×r-t，这个式子该怎么用我自己想不透，看了别人的分析才恍然大悟，s=n×r-t的意思不就是，如果一个指针p1从头开始走，另一个指针p2从相遇点开始走，则p1走到距离s处（即相遇点）时，p2走的距离为n×r-t，而n×r-t就是从相遇点绕环n圈后到环入口的距离，所以p2此时肯定也位于环入口处。
结论就是：
快慢指针第一次相遇后，一个指针从头开始以步长1前进，另一个指针继续从相遇点开始以步长1前进，则下一次相遇点就是环入口。

代码如下：

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                //快指针从头开始以步长1前进，满指针继续前进
                fast = head;
                while(fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;//下次相遇位置就是环入口
            }
        }
        return null;
    }
}

public class LinkedListCycle2 {
    public static void main(String[] args){
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        ListNode fourth = new ListNode(4);
        head.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = second;
        Solution solution = new Solution();
        if(solution.detectCycle(head)!=null)
            System.out.println(solution.detectCycle(head).val);
        else
            System.out.println("null");
    }
}

有环单链表是非常经典的面试题，我要专门写篇文章做总结。

---

GitHub代码

algorithms/leetcode/leetcode/_142_LinkedListCycle2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_142_LinkedListCycle2.java

---