The Linked List Cycle problem is:
Given a linked list, determine if it has a cycle in it. Can you solve it without using extra space?
A follow up problem is:
Given a linked list, return the node where the cycle begins. If there is no cycle, return
null
.Can you solve it without using extra space?
The first problem can be solved by the Floyd’s Cycle-Finding Algorithm:
Traverse linked list using two pointers: move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.
As for the second problem, it is also based on the Floyd’s Cycle-Finding Algorithm. However, after detecting loop, we need to find the starting point of the cycle. The most convinient way is to use two pointers, one points to the head node, and the other points to the node that pointers meet when detecting loop. Then move both the two pointers by one respectively in each iteration, until they meet. The node they meet is the starting point of the cycle.
Here is the detailed explanation of above trick(reference: http://www.cnblogs.com/TenosDoIt/p/3416702.html).
- Assume the length(number of nodes, the same below) of the list is
l
, the distance(number of nodes, the same below) betweenhead
and the starting point of cycle isa
, the distance between the cycle-starting point and the point where the slow/fast pointers meet isb
, and the length of the cycle isr
. - Assume when the fast/slow pointers meet, the slow pointer has accessed
s
nodes. Then the fast pointer has moved2s
, ands=a+b
. - Since the nodes accessed by the fast pointer also calculated as
kr+s
, wherek
is the number of cycles and \( k \ge 1 \). We have2s=kr+s
, i.e.s=kr
. - Since
s=a+b
ands=kr
, we havea+b=kr=(k-1)r+r
. Sincer=l-a
, we havea+b=(k-1)+l-a
, i.e.a=(k-1)+l-a-b
. Notice thatl-a-b
is the distance from the point where slow/fast pointers meet to the starting point of cycle(note: we only can go through the cycle of the linked list in one direction). - Since
a
is the distance betweenhead
node and the starting point of cycle,a=(k-1)+l-a-b
means that the distance betweenhead
node and the starting point of cycle(a
) equals to the distance from the point where slow/fast pointers meet to the starting point of cycle(l-a-b
) plus several loops of the cycle. - Therefore, when we use two pointers to find the starting point of cycle, one pointer moves to the start point from the head of the list, while the other pointer winds aroung the cycle at the same pace. When the two pointers meet, one pointer must have moved
a
and the other moved(k-1)+l-a-b
.
Following is my C++ implmentation.
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head==NULL || head->next==NULL)
return NULL;
ListNode* first=head;
ListNode* second=head;
while(first!=NULL && second!=NULL && second->next!=NULL) {
first=first->next;
second=second->next->next;
if(first==second)
break;
}
if(first==second) {
// Continue walking X steps
first = head;
while(first!=second)
{
first = first->next;
second = second->next;
}
return second;
} else {
return NULL;
}
}
// Create list with cycle using given vector of integers.
// lb - the beginning index(in vec) of the cycle.
ListNode* createList(vector<int>& vec, int lb) {
head=new ListNode(vec[0]);
ListNode* node=head;
ListNode* begin=NULL;
for(int i=1;i<vec.size();++i) {
node->next=new ListNode(vec[i]);
node=node->next;
if(i==lb)
begin=node;
}
if(lb>0 && lb<vec.size())
node->next=begin;
else if(lb>=vec.size()) // index out of upper bound, set to NULL
node->next=NULL;
else
node->next=head; // index out of lower bound, linked to the head
return head;
}
void printList(ListNode *head) {
ListNode* node=head;
while(node!=NULL) {
cout<<node->val<<" ";
node=node->next;
}
cout<<endl;
}
Solution() {head=NULL;}
~Solution() {
ListNode* node=head;
while(head!=NULL){
head=head->next;
delete node;
node=head;
}
}
private:
ListNode* head;
};