[LeetCode 142] Linked List Cycle II

作者 Shilei Tian 日期 2017-07-10
[LeetCode 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?

解题思路

题目要求判断一个链表是否有环,如果有,找到环路开始的地方。一个简单粗暴的方法,就是利用 C++11 的新特性 unordered_map,记录访问过的链表节点,一旦遇到访问过的,那么该节点就是环路开始的地方;如果链表到头了,则说明链表没有环路。时间复杂度 $O(n)$,空间复杂度 $O(n)$。

那么我们想,有没有常数级空间复杂度的算法?有的,本文就介绍一种速度非常快且空间复杂度为常数的算法。如果单纯想判断链表是否有环路,一个流行的思路是设置两个指针 slowfast,让这两个指针,slow 每次前进一步,fast 每次前进两步,判断两个指针是否重合,一旦重合,就说明有环路。那么找到环路开始的地方能不能借鉴这个思路呢?假设,slowfast 重合的时候,slow 一共经过了 $k$ 个节点,那么 fast 经过了 $2k$ 个节点,因此,我们可以得到:$2k-k=rn$,其中,$r$ 为环路一圈的节点数,$n$ 为 slowfast 相差的圈数。化简可得,$k=rn$。然后假设,链表非环路部分的节点数为 $s$,slow 在环路上经过的节点个数位 $m$,那么我们可以得到 $s+m=k$。我们如果能得到 $s$,然后我们从头节点开始走 $s$ 个节点,那么我们就得到了环路开始的位置。根据上式,$s=k-m=rn-m=(n-1)r+r-m$。这是一个多元函数,那么如果我们令 $n=1$,那么我们就可以求得 $s=r-m$。注意到,$r-m$ 是什么?实际上它就是重合点到环路起点剩下的节点数,这个值等于链表头节点到环路起点的长度。我们现在已经拿到重合点,又可以拿到头节点,那么是不是我们让两个指针每次移动一个节点的位置,当二者重合的时候,就是重合点的位置?

非常有趣的思路!代码如下:

class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* slow = head, * fast = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast) {
break;
}
}
if (fast == nullptr || fast->next == nullptr) {
return nullptr;
}
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};