142. Linked List Cycle II
Problem Description
The problem presents a linked list and asks us to determine where a cycle begins within it. A cycle in a linked list happens when a node's next
reference points back to a previous node in the list, causing a portion of the list to be traversed endlessly. We are given the head of the linked list, and we must find the node at which this cycle starts. If there is no cycle, our function should return null
.
A linked list cycle is conceptually akin to a running track, where the entry point of the cycle is the "gate" to the track, and the cycle itself is the loop. Our goal is to figure out where this "gate" is located within the list.
Intuition
To resolve the problem of finding out the cycle’s starting point, we can use the two-pointer technique, which is efficient and doesn't require extra memory for storage.
The intuition behind this algorithm involves a faster runner (the fast
pointer) and a slower runner (the slow
pointer), both starting at the head of the linked list. The fast
pointer moves two steps at a time while the slow
pointer moves only one. If a cycle exists, the fast
pointer will eventually lap the slow
pointer within the cycle, indicating that a cycle is present.
Once they meet, we can find the start of the cycle. To do this, we set up another pointer, called ans
, at the head of the list and move it at the same pace as the slow
pointer. The place where ans
and the slow
pointer meet again will be the starting node of the cycle.
Why does this work? If we consider that the distance from the list head to the cycle entrance is x
, and the distance from the entrance to the meeting point is y
, with the remaining distance back to the entrance being z
, we can make an equation. Since the fast
pointer travels the distance of x + y + n * (y + z)
(where n
is the number of laps made) and slow
travels x + y
, and fast
is twice as fast as slow
, then we can deduce that x = n * (y + z) - y
, which simplifies to x = (n - 1) * (y + z) + z
. This shows that starting a pointer at the head (x
distance to the entrance) and one at the meeting point (z
distance to the entrance) and moving them at the same speed will cause them to meet exactly at the entrance of the cycle.
Learn more about Linked List and Two Pointers patterns.
Solution Approach
In this solution, we use the two-pointer technique, which involves having two iterators moving through the linked list at different speeds: slow
and fast
. slow
moves one node at a time, while fast
moves two nodes at a time.
The algorithm is divided into two main phases:
-
Detecting the cycle: Initially, both
slow
andfast
are set to start at the head of the list. We then enter a loop in whichfast
advances two nodes andslow
advances one node at a time. If there is no cycle, thefast
pointer will eventually reach the end of the list and we can returnnull
at this point, as there is no cycle to find the entrance of.However, if there is a cycle,
fast
is guaranteed to meetslow
at some point within the cycle. The meeting point is not necessarily the entrance to the cycle, but it indicates that a cycle does exist. -
Finding the cycle starting node: When
fast
andslow
meet, we introduce a new pointer calledans
and set it to the head of the list. Now, we move bothans
andslow
one node at a time. The node at which they conjoin is the start of the cycle.
Why does the above approach lead us to the start of the cycle? We derive this from the fact that:
- The distance from the list's head to the cycle's entrance is denoted as
x
. - The distance from the cycle's entrance to the first meeting point is
y
. - The remaining distance from the meeting point back to the entrance is
z
.
Using these variables, we know that when fast
and slow
meet, fast
has traveled x + y + n * (y + z)
which is the distance to the meeting point plus n
laps of the cycle.
Since fast
travels at twice the speed of slow
, the distance slow
has traveled (x + y
) is half that of fast
, leading us to the equation 2(x + y) = x + y + n * (y + z)
. Simplifying this, we find x = (n - 1)(y + z) + z
.
This equation essentially states that the distance from the head to the cycle entrance (x
) is equal to the distance from the meeting point to the entrance (z
) plus some multiple of the cycle's perimeter (y + z
). This is why moving the ans
pointer from the head and slow
from the meeting point at the same pace will lead them to meet at the cycle's entrance.
The Python code provided implements this approach efficiently, using only two extra pointers (fast
and slow
) for detection and one extra (ans
) for locating the cycle's entrance.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple linked list example to walk through the solution approach:
Suppose we have the linked list 1 -> 2 -> 3 -> 4 -> 5 -> 2
(the last node points back to the second one, creating a cycle). Here, the node with the value 2
is the start of the cycle.
-
Detecting the cycle:
- Initially, both
slow
andfast
pointers are at the head of the list (node with value1
). - Move
slow
to the next node (2
) andfast
two nodes forward (3
). - Move
slow
to the next node (3
) andfast
two nodes forward (5
). - Continue this process until
fast
andslow
meet. In our case, after few iterations,fast
andslow
both point to one of the nodes inside the cycle (let's say they meet at node with value4
).
- Initially, both
-
Finding the cycle starting node:
- Place the
ans
pointer at the head of the list (node with value1
). - Move
ans
to the next node (2
) andslow
to the next node (5
). - Continue moving both
ans
andslow
one node at a time. As the pointers move one step each turn, they will meet at the node that is the start of the cycle. - In our case,
ans
andslow
will both meet at the node with value2
, which is the correct entrance to the cycle.
- Place the
By following these steps and the reasonings behind the solution approach, we are able to find that the node with the value 2
is the entry point of the cycle in the linked list without using any extra memory for storage, only the two pointer variables fast
, slow
, and later the ans
pointer.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, value=0, next=None):
4 self.value = value
5 self.next = next
6
7class Solution:
8 def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
9 # Initialize two pointers, slow and fast
10 slow = fast = head
11
12 # Traverse the linked list with two pointers moving at different speeds
13 while fast and fast.next:
14 slow = slow.next # Slow pointer moves one step
15 fast = fast.next.next # Fast pointer moves two steps
16
17 # Check if the slow and fast pointers meet, indicating a cycle
18 if slow == fast:
19 # Initialize another pointer to the head of the linked list
20 start = head
21
22 # Move both pointers at the same speed until they meet at the cycle's start node
23 while start != slow:
24 start = start.next
25 slow = slow.next
26
27 # Return the node where the cycle begins
28 return start
29
30 # If no cycle is detected, return None
31 return None
32
1// Definition for singly-linked list.
2class ListNode {
3 int val;
4 ListNode next;
5
6 ListNode(int x) {
7 val = x;
8 next = null;
9 }
10}
11
12public class Solution {
13 // This method detects the node where the cycle begins in a linked list
14 public ListNode detectCycle(ListNode head) {
15 // Two pointers initialized to the start of the list
16 ListNode fast = head;
17 ListNode slow = head;
18
19 // Loop until the fast pointer reaches the end of the list
20 while (fast != null && fast.next != null) {
21 // Move the slow pointer by one step
22 slow = slow.next;
23 // Move the fast pointer by two steps
24 fast = fast.next.next;
25 // If they meet, a cycle is detected
26 if (slow == fast) {
27 // Initialize another pointer to the start of the list
28 ListNode start = head;
29 // Move both pointers at the same pace
30 while (start != slow) {
31 // Move each pointer by one step
32 start = start.next;
33 slow = slow.next;
34 }
35 // When they meet again, it's the start of the cycle
36 return start;
37 }
38 }
39 // If we reach here, no cycle was detected
40 return null;
41 }
42}
43
1// Definition for singly-linked list.
2struct ListNode {
3 int val;
4 ListNode *next;
5 ListNode(int x) : val(x), next(nullptr) {}
6};
7
8class Solution {
9public:
10 // This function detects a cycle in a linked list and returns the node
11 // where the cycle begins. If there is no cycle, it returns nullptr.
12 ListNode* detectCycle(ListNode* head) {
13 ListNode* fastPointer = head; // Fast pointer will move two steps at a time
14 ListNode* slowPointer = head; // Slow pointer will move one step at a time
15
16 // Loop until the fast pointer reaches the end of the list,
17 // or until the fast and slow pointers meet, indicating a cycle.
18 while (fastPointer && fastPointer->next) {
19 slowPointer = slowPointer->next; // Move slow pointer one step
20 fastPointer = fastPointer->next->next; // Move fast pointer two steps
21
22 // Check if the slow and fast pointers have met, indicating a cycle.
23 if (slowPointer == fastPointer) {
24 ListNode* entryPoint = head; // Start from the head
25
26 // Loop until the entry point of the cycle is found.
27 while (entryPoint != slowPointer) {
28 entryPoint = entryPoint->next; // Move entry point one step
29 slowPointer = slowPointer->next; // Move slow pointer one step
30 }
31
32 // The entry point is where the slow pointer and entry point meet.
33 return entryPoint;
34 }
35 }
36
37 // If the loop exits without the pointers meeting, there is no cycle.
38 return nullptr;
39 }
40};
41
1// Definition for singly-linked list node.
2interface ListNode {
3 val: number;
4 next: ListNode | null;
5}
6
7/**
8 * Detects a cycle in a linked list and returns the node where the cycle begins.
9 * If there is no cycle, it returns null.
10 * @param head - The head of the singly-linked list.
11 * @returns The node where the cycle begins or null if no cycle exists.
12 */
13function detectCycle(head: ListNode | null): ListNode | null {
14 // Initialize two pointers, slow and fast.
15 let slow: ListNode | null = head;
16 let fast: ListNode | null = head;
17
18 // Traverse the list with two pointers moving at different speeds.
19 while (fast !== null && fast.next !== null) {
20 slow = slow!.next; // Move slow pointer one step.
21 fast = fast.next.next; // Move fast pointer two steps.
22
23 // If slow and fast pointers meet, a cycle exists.
24 if (slow === fast) {
25 // Initialize another pointer to the beginning of the list.
26 let startPoint: ListNode | null = head;
27 // Move the startPoint and slow pointer at the same speed.
28 while (startPoint !== slow) {
29 startPoint = startPoint!.next;
30 slow = slow!.next;
31 }
32 // The node where both pointers meet is the start of the cycle.
33 return startPoint;
34 }
35 }
36
37 // If no cycle is detected, return null.
38 return null;
39}
40
Time and Space Complexity
The time complexity of the code is O(n)
, where n
is the number of nodes in the linked list. This is because in the worst case, both fast
and slow
pointers traverse the entire list to detect a cycle, and then a second pass is made from the head
to the point of intersection which is also linear in time.
The space complexity of the code is O(1)
. This is due to the fact that no additional space proportional to the size of the input linked list is being allocated; only a fixed number of pointer variables fast
, slow
, and ans
are used, irrespective of the size of the linked list.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear? Submit the part you don't understand to our editors. Or join our Discord and ask the community.