## 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?

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

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.

ReplyDeletepure circular is covered by his solution, becoz a init head is given, which will be returned by his solution anyway.

ReplyDeletet = (n-k) should be t = (n-(k mod n))

Can someone please explaine why do we reassign only fast pointer?

ReplyDeleteq = head

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

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

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

ReplyDelete