142. Linked List Cycle II (Medium) !

Q:

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

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.

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

A:
Use HashSet

/**

* 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) {

unordered_set<ListNode*> S;

while (head) {

if (S.find(head) != S.end()) {

return head;

}

S.insert(head);

head = head->next;

}

return nullptr;

}

};

就用CC150上的那道题目。  先slow and fast runner meet后，再把fast 放到开头，重新跑（速度变正常）



Mistakes:

1： update fastRunner 到链表头的时候，忘了把slowRunner也往下走一个。

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

证明如下：
假设前面不重复的链表长度为k,     # of nodes in circle is n.
at time t = k+a   (where a is the number of nodes slow have run in the circle)
=======>  a+k = 2(k+a) - x*n ,  (x倍的n), 取代了求模运算
则有 a+k = x*n
那么，fast再走 k时间，也就是再走 (a +k) 的时候，就回到了原点。
这里有一个注意的地方就是，（当我们重新计数的时候，slow=head时，已经表明我们走了一步了。因此我们需要把fast也前进一步。


Learned: