0%

Leetcode Solution: #142 Linked List Circle

Description

Given a linked list and return where the circle begins. For example, a linked list $[3, 2, 0, 4]$ having circle $[2, 0, 4]$ is shown below.

Linked_circle

The algorithm should return the second node. I use C++ to solve this problem and define the node as below.

1
2
3
4
5
6
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

Solution 1: hashset

A trivial idea to solve this problem is saving the node information in a hashset when traversing and find if there is a visited node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *cur = head;
unordered_set<ListNode*> storage;
while(cur!=NULL){
if (storage.find(cur)!=storage.end()){
return cur;
}
storage.insert(cur);
cur = cur->next;
}
return NULL;
}
};

This is a method with O(n) time complexity and O(n) space complexity. But if there is a method to solve this problem with O(1) space complexity?

Solution 2: fast and slow pointers

Set two pointers which slower one move one time one step and faster one move one time two steps. Once they meet, reset the faster one to the head pointer, then finally they will meet in the begin node of circle. This is an algorithm without extra space. But why it works?

There is a mathematical idea. Suppose the distance from head node to the begin of circle is $x_1$, the distance from begin of circle and meeting point on the circle is $x_2$, the distance from meeting point back to the begin of the circle is $x_3$. Then there is the velocity equation.

It means that the difference between $x_3$ and $x_1$ is the multiple of circle length. Due to the definition of $x_3$ and $x_1$, if the fast pointer move from the head node when the slow pointer move from the meeting point, finally the slow pointer and fast pointer will meet on the begin of the circle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL || head->next == NULL || head->next->next == NULL) return NULL;
ListNode* fast = head->next->next;
ListNode* slow = head->next;
while(fast != slow){
if(fast->next == NULL || fast->next->next == NULL) return NULL;
fast = fast->next->next;
slow = slow->next;
}
fast = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};

Don’t forget the special cases of NULL pointer and if fast pointer move to NULL means there is no circle.