leetcode Question: Linked List Cycle II

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

Analysis:


This problem can be viewed as two major steps:
    (1) Detect whether the loop exists in the linked list.
    (2) Find the loop start node if loop exists.

The (1) step can be easily solved using the slow&fast pointers (see Linked List Cycle)
How to deal with step (2)?

Firstly let us assume the slow pointer (S) and fast pointer (F) start at the same place in a n node circle. S run t steps while F can run 2t steps, we want to know what is t (where they meet) , then
just solve:  t mod n = 2t mod n,  it is not hard to know that when t = n, they meet, that is the start of the circle.

For our problem, we can consider the time when S enter the loop for the 1st time, which we assume k step from the head. At this time, the F is already in k step ahead in the loop. When will they meet next time?
Still solve the function:    t mod n = (k + 2t) mod n
Finally, we can find out: t = (n-k), S and F will meet, this is k steps before the start of the loop.

So, the Step (2) can be easily solved after Step(1):
Note that here S and F are not slow or fast pointers, but only regular pointers.
1. Set S to the head.
2. S = S -> next, F = F->next
3. output either one of the pointer until they meet.

Here I show some figure for better illustration:
Note that, from step 5, p (slow pointer) firstly enter the loop, it will go (n-k) steps, and meet with fast pointer q. The rest of step is n-(n-k) = k, steps from current meet point, back to the start of the loop.







Code(C++):


/**
 * 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){return NULL;}
        ListNode *p=head;
        ListNode *q=head;
        while (1){
            if (p->next!=NULL){p=p->next;}else{return NULL;}
            if (q->next!=NULL && q->next->next!=NULL){q=q->next->next;}else{return NULL;}
            if (p==q){ //if find the loop, then looking for the loop start
                q=head;
                while (p!=q){
                    p=p->next;
                    q=q->next;
                }
                return p;
            }
        }
    }
};

Code(python):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        p = head
        q = head
        while True:
            if p.next:
                p = p.next
            else:
                return None
            if q.next and q.next.next:
                q = q.next.next
            else:
                return None
            if p == q:
                q = head
                while p!=q:
                    p = p.next
                    q = q.next
                return p
            
            
            
        


5 comments:

  1. Have you ever consider a pure circular list case that every node can be considered as a start? Looks like you have to record the starting location of the slow pointer (and of course same as the fast pointer), when it meets the fast pointer, check if their location is same as the recorded location, if same, line 18 after are not needed, because you have a pure circular list.

    ReplyDelete
  2. pure circular is covered by his solution, becoz a init head is given, which will be returned by his solution anyway.
    t = (n-k) should be t = (n-(k mod n))

    ReplyDelete
  3. Can someone please explaine why do we reassign only fast pointer?
    q = head

    ReplyDelete
    Replies
    1. I have rewrite this post and added some figure, hope this could make you understand it better.

      Note that, here in this step, p and q are used as regular pointer (one step each time).

      Delete
  4. How did you get t = n-k from t mod n = (k+2t) mod n?

    ReplyDelete