LeetCode Linked List Cycle

Linked List Cycle I

题目描述

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

大意就是给你个单链表,让你判断有没有环。版本一比较简单,两个指针一个fast每次走两步,一个slow每次走一步,如果能相遇肯定有环,简单追击问题

bool hasCycle(ListNode *head) {
    if (!head) return false;
    ListNode* fast = head, *slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) return true;
    }
    return false;
}

Linked List Cycle II

题目描述

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

版本二就是让你找到相交的节点,这个就要比第一个难一些了

这个是需要一些证明的

假设 slow 走了 s 的距离, fast 走了 2s 的距离(因为一个速度是另一个的二倍
环的长度是r,他们相遇的时候在环上转了n圈(n > 0),n 肯定大于0,不可能一圈没走完就追上了

所以我们得出第一个结论

s = 2s - nr 公式(1)

fast 和 slow 的路程差是环的 n 圈,即追击的路程差,然后就得出了

2s - sn = s = nr 公式(2)

假设从 链表头环入口 距离为x,从 环入口相遇点 为y,我们得出了 slow 指针走过的距离

s = x + y 公式(3)

为什么没有 nr 呢?因为 fast 追上了 slow 试想一样他俩速度一快一慢,然后一个还转了好几圈才追上另一个?不太可能~

所以由(2)(3)两个公式得出 x + y = nr 公式(4)

即x = nr - y 公式(5)

你会发现其实 n 是可以消掉的

x = r - y 公式(5),这个就是我们要的结论

slow 指针刚好就在相遇点,他距离 entry 是r - y,和x是一样的

所以把 fast 指针移回 head 节点,步数变为1,当他们相遇的时候,就是那个交点

代码如下

ListNode *detectCycle(ListNode *head) {
    bool hasCycle = false;
    ListNode *fast = head, *slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            hasCycle = true;
            break;
        }
    }
    if (!hasCycle)
        return nullptr;
    fast = head;
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}