10043. LinkedList Cycle starting point

Given a linked list. Return pointer to the node where cycle starts. If there is no cycle, return null.

Definition of a single linked list:

//Java

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

// C++

class ListNode

{

public:

int val;

ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};

Implement a function detectCycle that returns a pointer to the node where cycle starts. If there is no cycle, return null.

// Java

ListNode detectCycle(ListNode head)

// C++

ListNode* detectCycle(ListNode *head)

Example

Function detectCycle returns null because this linked list does not contain a cycle.

Function detectCycle returns pointer to the node with value 3 – the starting point of the cycle.

SOLUTION

linked list

Algorithm analysis

Using two pointers (slow and fast), we determine whether the linked list contains a loop. Let the list contains a loop, and p points to the vertex where the fast pointer meets with the slow one. Set q to the start of the list.

Let the distance from the start to the vertex where the cycle starts is x. The distance from the start of the loop to the meeting point of two pointers is y. The distance from the vertex pointed to by p to the beginning of the cycle along the list is z.

Suppose the pointers have met so that the fast pointer has only gone one round of the cycle. That is, the slow one went the path x + y, and the fast one x + y + z + y. Considering that a fast pointer is twice as fast as a slow one, we get an equality:

2 (x + y) = x + y + z + y or x = z

This means that now it is enough to iteratively move the pointers p and q step by step until they become equal (will point to the same memory location). Moreover, this will definitely happen at the node, which is the beginning of the cycle.

Algorithm realization

ListNode* detectCycle(ListNode *head)

{

if (!head) return NULL;

Set up the pointers p and q to the start of the list.

ListNode* p = head;

ListNode* q = head;

While there are at least two elements behind the q pointer (the fast pointer can be moved two steps forward), we continue the loop.

while (q->next && q->next->next)

{

p = p->next;

q = q->next->next;

If pointers are equal, they point to the same memory location. The fast pointer q caught up the slow p, the list contains a cycle.

if (p == q)

{

Set up the pointer q to the start of the list.

q = head;

Move the pointers p and q forward one position until they meet.

while (p != q)

{

p = p->next;

q = q->next;

}

Pointers p and q will meet at the node, which is the start of the cycle. Return a pointer to this node.

return p;

}

}

There is no cycle, return null.

return NULL;

}

Java realization

ListNode detectCycle(ListNode head)

{

if (head == null) return null;

ListNode p = head;

ListNode q = head;

while(q.next != null && q.next.next != null)

{

p = p.next;

q = q.next.next;

if (p == q)

{

q = head;

while (p != q)

{

p = p.next;

q = q.next;

}

return p;

}

}

return null;

}