Check if a linked list is circular linked list leetcode

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