单链表中的环问题

发表于 | 分类于

1. 来源

  • LeetCode 141 - Linked List Cycle

Given a linked list, determine if it has a cycle in it.

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

  • LeeCode 142 - Linked List Cycle II

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?

2. 判断是否有环

双指针问题，设置两个指针 fast 和 slow，初始均指向 head 节点。fast 指针每次走两步，slow 指针每次走一步。若 fast 指针或 fast.next 指针为 null，则无环；当 fast == slow 则有环。

3. 计算环的位置

假设环的连接点为 joint，head 到 joint 的步长为 $x$，环长为 $L$， fast 和 slow 指针在交汇时经过了 $t$ 个步骤，交汇点 intersection 沿链表方向距离 joint 的步长为 $y$。则
$$
t=x+(L-y)\
2t=x+(L-y)+nL
$$
其中 $n$ 为交汇时 fast 指针已经在环上走过的圈数。可得：
$$
x=(n-1)L+y
$$
这个式子的含义是，head 到 joint 的距离，等于 intersection 到 joint 的距离加上环长的整数倍。

那么，让两个指针一个从 head 出发，一个从 intersection 出发，经过相同的步数（即 $x$）之后，他们应当在 joint 相汇。

LeetCode 142 Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode detectCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while(true) {
        if(fast == null || fast.next == null) return null;
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow) break;
    }
    while(head != slow) {
        head = head.next;
        slow = slow.next;
    }
    return head;
}

4. 其他问题

  • 怎么求环长？

fast 和 slow 交汇后，让 slow 再走一圈即得到环长。

或者先得到环的连接点，再从连接点开始走一圈环。

  • 怎么得到单链表总长？

在计算环的连接点时，可以计算出 $x$，再加上环长。