问题

142.环形链表 II

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

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

不允许修改 链表。

示例

输入：head = [3,2,0,-4], pos = 1

输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。

练习

环形链表

# your python code

思路

北海啊，要多想！

快慢指针

设头节点到环入口的距离（节点数 -1）为 a。环入口到快慢指针相遇点的距离为 b。相遇点到环入口的距离为 c（即环的剩余部分）。

[头节点] ----a----> [环入口] ----b----> [相遇点]
                    ↑                   |
                    |_________c_________|

当我们设置快、慢指针从头节点开始出发到相遇时：

• 慢指针走的步数：a + b（因为进入环后最多走一圈就会和快指针相遇）。
• 快指针走的步数：a + b + k*(b + c)（比慢指针多走 k 圈环，k ≥ 1）。

由于快指针速度是慢指针的 2 倍，则 2(a + b) = a + b + k*L，从而 a = (k - 1)*L + c。这表明，从相遇点到环入口的距离 c 和从头节点到环入口的距离 a 的关系是：a 等于 c 加上整数倍环长。

因此，如果再令两个指针分别从头节点和相遇点出发，每次走一步，它们一定会在环入口相遇。

Java

import utils.LinkedListUtils;  
import utils.LinkedListUtils.ListNode;  
  
public class LC142DetectCycle {  
    public static void main(String[] args) {  
        int[] list = {-4, 1};  
        int pos = -1;  
        ListNode head = LinkedListUtils.createListWithCircle(list, pos);  
        LinkedListUtils.printList(head);  
  
        System.out.println(detectCycle(head));  
    }  
    private static ListNode detectCycle(ListNode head) {  
        ListNode fast = head, slow = head;  
        while (fast != null) {  
            slow = slow.next;  
            if (fast.next == null) {  
                return null;  
            }            
            fast = fast.next.next;  
  
            if (fast == slow) {  
                ListNode cur = head;  
                while (cur != slow) {  
                    slow = slow.next;  
                    cur = cur.next;  
                }                
                return cur;  
            }        
        }  
        return null;  
    }
}

复杂度分析：

• 时间复杂度：$\mathcal{O}(N)$。
• 空间复杂度：$\mathcal{O}(1)$。