LeetCode142-环形链表II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/linked-list-cycle-ii/

中文链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/

题目详述

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

说明：不允许修改给定的链表。

进阶：
你是否可以不用额外空间解决此题？

题目详解

  • 使用双指针，一个快指针，一个慢指针。快指针每次走两步，慢指针每次走一步。

  • 如果存在环，两个指针必然会在环上的某个结点相遇。

  • 设 a 为起点 A 到环入口点 C（图中黑色部分）的长度，b 为环入口点 C 到相遇点 B（图中蓝色部分）的长度，L 为环的长度，当两个指针相遇的时候，快指针走的路程 s1 = a + m * L + b，s2 = a + n * L + b。

  • 因为快指针的速度的大小是慢指针的两倍，故 s1 = 2 * s2。

  • 则 a + m * L + b = 2 * (a + n * L + b)，

  • m * L = 2 * n * L + a + b，

  • a = (m - 2 * n) * L - b，

  • a = (m - 2 * n - 1) * L + L - b。而 L - b 是相遇点 B 到环入口点 C 的长度。

  • 有了上面的分析可知，在两个指针相遇后，让两个指针分别从 A 和 B 同步走，最后相遇的结点就是环的入口结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class LeetCode_00142 {

    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}