142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

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

Thoughts

linked list里如有环，返回环开始的位置。两个指针从head开始快慢跑，在一个环上跑得快的肯定会在某点追上跑的慢的。假设已经相遇，a: 环之前长度, c: 环长度, s: slow走的步数, k: 环起点后第k步相遇，x: slow跑得环的圈数，y: fast跑得圈数，因此 s=a+xc+k, 2s=a+yc+k, 合并得k = (y-2x)b-a, 即slow还差a步则走的步数刚好又是环长的倍数，也就是说slow里环终点(起点)还差a步，因此让slow和head再走a步它们刚好会相遇。

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto slow = head, fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                while (head != slow) {
                    head = head->next;
                    slow = slow->next;
                }
                return head;
            }
        }
        return nullptr;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = slow;
        while (slow != null && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return slow;
            }
        }

        return null;
    }
}

Analysis:

Errors:

1. 终止条件是slow.next == head， 不是slow == head或者head.next == slow

TC: O(n)

我们来分析一下，时间复杂度取决于slow到底走了多少步，即a + xc + k 和总结点数N关系。 主要就是看x是多少。 我们知道x取决去fast什么时候能追上slow. 由于fast先走，等slow进环时fast早已在环中等候了。 那在一个环里slow最多能走多少就被fast追上呢？答案是不到一个环。 我们假设最差的情况，即fast和slow刚好差一个环的位置，那么s_f = s + c, 即2s = s + c, s = c.也就是说在fast和slow在环中起始位置刚好差一个环时，slow最多走一个环就会被追上。 又由于fast和slow实际最多只能差c - 1, 所以x < 1, s < a+2c。整个算法是O(N)级别。