142. Linked List Cycle II

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

Note:Do not modify the linked list.

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

Thoughts

1. Having two pointers: slow vs fast. When two first meets, note slow has gone k steps. So for the faster pointer, which is ahead of slow pointer exactly the length of cycle, r. Since faster at that moment can be counted as 2k steps. Then 2k = k + r => k = r. Also, note s as the distance between the start node of the list and the start node of the cycle, m as the distance between the start node of cycle and the first meeting node. k = s + m => s = k - m = r - m (the rest distance to finish the cycle, or the distance to REACH the start node of the cycle).

2. Solution: use hasCycle to detect whether there is an cycle. if there is an cycle, reset the slow pointer to the head then both move slow and fast one step each time until they first meet. The node they meet is the answer.

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) {
        if (head == NULL || head->next == NULL) return NULL;

        ListNode* slow = head;
        ListNode* fast = head;
        bool isCycle = false;

        while(fast->next && fast->next->next){
            slow = slow ->next; 
            fast = fast ->next -> next;
            if(slow == fast) {isCycle =true; break;}
        }


        if(!isCycle) return NULL;
        slow = head;
        while( slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

Special Thanks wall0p's Ideas + Solution