Share my O(n) complexity and constant space code. Keep the original list. Any comments.


  • 6
    W

    The idea is :

    1. First, scanning the list using slow and fast pointers, and using slowVal, fastVal records the steps two pointers have past. If the list has loop, then fastVal - slowVal equals the size of the loop.
    2. Then, let slow points head, and fast points loopSize ahead.
    3. Let slow and fast points the next until slow == fast, here we found the begin of the loop.

    Here, we scan the list twice, and use constant space.
    The code:

    ListNode *detectCycle(ListNode *head) {
    	if (head == NULL){
    		return NULL;
    	}
    	ListNode *slow = head, *fast = slow->next;
    	long long slowVal = 0, fastVal = slowVal + 1;
    	while (fast != NULL){
    		if (slow == fast){
    			break;
    		}
    		slow = slow->next;
    		fast = fast->next;
    		++slowVal;
    		++fastVal;
    		if (fast != NULL){
    			fast = fast->next;
    			++fastVal;
    		}
    	}
    	// No loop
    	if (fast == NULL){
    		return NULL;
    	}
    	long long loopSize = fastVal - slowVal;
    	slow = fast = head;
    	while (loopSize){
    		fast = fast->next;
    		--loopSize;
    	}
    	while (slow != fast){
    		slow = slow->next;
    		fast = fast->next;
    	}
    	return fast;
    }
    

    Any comments are welcome.


  • 29
    Q

    slowVal and fastVal are unnecessary. When fast == slow , they just point loopSize. So the code can be simplified as follows,

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

  • 0
    W

    Thanks very much for your advice! That exactly makes the code more concise.


  • 0
    G

    If the list is 1-2-3-4 and 4 links back to 2, your solution returns 4. Is it correct? I expect it to return 2.


  • 0
    G

    fastVal - slowVal is not necessary loopsize. It is multiple of loopsize. Consider 1-2-3-4-5, 5 links back to 4.


  • 0
    W

    I guess that the 1-2-3-4 input is not correct for the case that 4 links back to 2, maybe 1-2-3-4-2? And my method will return 2. Thanks about your advice and I also find the fastVal and slowVal is not necessary:)


  • 14
    L

    Just a bit more explanation on the math logic behind the above algorithm.

    Assume that the distance from the head of the list to the joint point of the ring is K. The size of the ring is RING_SIZE. (Note: here we assume RING_SIZE > K. It is easy to derive the proof for the case where RING_SIZE < K). Two pointers: slow and fast; the slow pointer moves one step at a time, and the fast pointer moves two steps at a time.

    The algorithm locates the joint point of the ring within a linked list, in O(N) time complexity and constant space complexity, via the following steps.

    1. Both pointers start from the head of list. In K steps, the slow
      pointer reaches the joint point, while the fast pointer is K steps
      away from the joint point, since the fast pointer moves two times
      faster than the slow one. In other words, we could say that the
      fast pointer is (RING_SIZE - K) lagging behind the slow pointer, if
      the movement continues.

    2. To catch up with the slow pointer, it takes 2*(RING_SIZE-K)
      steps for the fast pointer. At the same time, the slow pointer is
      (RING_SIZE-K) away from the joint point. In other words, both
      pointers now, are (RING_SIZE - (RING_SIZE-K)) = K steps to the joint
      point.

    3. Now we could move the slow pointer to the head of the list, and
      keep the fast pointer at the first meeting point. Now, if both
      pointers move at the same pace, one step at a time, they would meet
      again, in K steps. And this time, as we can see from the step 2),
      they would meet at the joint point.


  • 0
    W

    Thx about your explanation on the math!


  • 0
    R

    much appreciate! I figure it out after reading your explanation.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.