141. Linked List Cycle
Problem Description
The problem provides us with the head of a singly-linked list and asks us to determine whether there is a cycle within this linked list. A cycle exists if a node's next
pointer points to a previously traversed node, meaning one could loop indefinitely within the linked list. We do not have access to the pos
variable which indicates the node that the last node is connected to (forming the cycle). Our goal is to figure out whether such a cycle exists by returning true
if it does or false
otherwise.
Intuition
The intuition behind the solution relies on the "tortoise and the hare" algorithm, or Floyd's cycle-finding algorithm. The core idea is to use two pointers, a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
If the linked list has no cycle, the fast pointer will eventually reach the end of the list (null).
If the linked list has a cycle, the fast pointer will start looping within the cycle and eventually both pointers will be inside the cycle. Given that the fast pointer moves twice as fast as the slow pointer, it will catch up to the slow pointer from behind, meeting at some node within the cycle. This is reminiscent of a track where a faster runner laps a slower runner.
Once both pointers occupy the same node (they meet), we can confirm that a cycle exists and return true
. If the while loop terminates (fast pointer reaches the list's end), we return false
as no cycle is present.
Learn more about Linked List and Two Pointers patterns.
Solution Approach
The solution uses the Floyd's cycle-finding algorithm. We initialize two pointers, slow
and fast
, and both of them start at the head of the linked list.
While traversing the list:
- The
slow
pointer is moved by one node at a time usingslow.next
. - The
fast
pointer is moved by two nodes at a time usingfast.next.next
.
This means after each iteration through our loop, fast
is two nodes ahead of slow
(assuming they don't yet point to the same node and the fast
pointer has not encountered the end of the list).
- If the linked list has no cycle, the
fast
pointer will reach a node that has anull
next
pointer and the loop will end, hence the conditionwhile fast and fast.next:
in our loop. - If there is a cycle,
fast
will eventually meetslow
inside the cycle, since it moves twice as fast and will thus close the gap between them by one node per step inside the cycle.
The loop continues until either fast
reaches the end of the list (indicating there is no cycle), or fast
and slow
meet (indicating there is a cycle). If fast
and slow
meet (i.e., slow == fast
), we return true
. If the loop ends without them meeting, we return false
.
Here is a pseudo-code breakdown of the algorithm:
initialize slow and fast pointers at head while fast is not null and fast.next is not null move slow pointer to slow.next move fast pointer to fast.next.next if slow is the same as fast return true (cycle detected) return false (no cycle since fast reached the end)
The crux of the method is that the existence of a cycle is exposed by the movement of the fast
pointer in relation to the slow
pointer. If they ever point to the same node, it means there is a cycle because the fast
pointer must have lapped the slow
pointer somewhere within the cycle.
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 say we have the following linked list where the last node points back to the second node, forming a cycle:
1 -> 2 -> 3 -> 4 -> 5
^ |
|_________|
To illustrate the solution approach with this example:
-
We initialize two pointers at the head:
slow
is at node1
fast
is at node1
-
We then start iterating through the list:
- Move
slow
to the next node (2
), movefast
two nodes ahead (3
).
- Move
-
On the next iteration:
- Move
slow
to3
, movefast
to5
.
- Move
-
Next iteration:
- Move
slow
to4
, movefast
two nodes ahead but because of the cycle, it lands on2
.
- Move
-
On the following iteration:
- Move
slow
to5
,fast
moves to4
.
- Move
At this point the loop continues:
-
slow
moves to node2
(following the cycle) andfast
to node3
. -
Next,
slow
moves to3
andfast
jumps two steps, landing on5
again. -
Finally,
slow
goes to4
andfast
which is at5
now makes a two-step jump and lands on4
, meeting theslow
pointer.
Since slow
and fast
are both pointing to 4
, this is evidence of a cycle. Thus, we return true
.
If at any point fast
or fast.next
were null, it would mean that fast
has reached the end of the linked list and there is no cycle, in which case we would return false
. However, in our example, as slow
and fast
meet, we have confirmed the presence of a cycle.
Solution Implementation
1class ListNode:
2 def __init__(self, value):
3 self.value = value
4 self.next = None
5
6
7class Solution:
8 def hasCycle(self, head: ListNode) -> bool:
9 # Initialize two pointers, slow and fast. Both start at the head of the list.
10 slow_pointer = fast_pointer = head
11
12 # Loop until fast_pointer reaches the end of the list
13 while fast_pointer and fast_pointer.next:
14 # Move slow_pointer by one step
15 slow_pointer = slow_pointer.next
16 # Move fast_pointer by two steps
17 fast_pointer = fast_pointer.next.next
18
19 # If slow_pointer and fast_pointer meet, there's a cycle
20 if slow_pointer == fast_pointer:
21 return True
22
23 # If fast_pointer reaches the end, there is no cycle
24 return False
25
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int value; // The value of the node.
6 ListNode next; // Reference to the next node in the list.
7
8 // Constructor to initialize the node with a specific value.
9 ListNode(int value) {
10 this.value = value;
11 this.next = null;
12 }
13}
14
15public class Solution {
16 /**
17 * Detects if there is a cycle in the linked list.
18 *
19 * @param head The head of the singly-linked list.
20 * @return true if there is a cycle, false otherwise.
21 */
22 public boolean hasCycle(ListNode head) {
23 // Initialize two pointers, the slow pointer moves one step at a time.
24 ListNode slow = head;
25 // The fast pointer moves two steps at a time.
26 ListNode fast = head;
27
28 // Keep traversing the list as long as the fast pointer and its next are not null.
29 while (fast != null && fast.next != null) {
30 // Move the slow pointer one step.
31 slow = slow.next;
32 // Move the fast pointer two steps.
33 fast = fast.next.next;
34
35 // If the slow and fast pointers meet, a cycle exists.
36 if (slow == fast) {
37 return true;
38 }
39 }
40 // If the loop ends without the pointers meeting, there is no cycle.
41 return false;
42 }
43}
44
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int value;
5 * ListNode *next;
6 * ListNode(int x) : value(x), next(nullptr) {}
7 * };
8 */
9class Solution {
10public:
11 // Checks if the linked list has a cycle
12 bool hasCycle(ListNode *head) {
13 ListNode *slowPointer = head; // Initialize slow pointer
14 ListNode *fastPointer = head; // Initialize fast pointer
15
16 // Loop until the fast pointer reaches the end of the list
17 while (fastPointer && fastPointer->next) {
18 slowPointer = slowPointer->next; // Move slow pointer by 1 node
19 fastPointer = fastPointer->next->next; // Move fast pointer by 2 nodes
20
21 // If both pointers meet at the same node, there is a cycle
22 if (slowPointer == fastPointer) {
23 return true;
24 }
25 }
26
27 // If the fast pointer reaches the end of the list, there is no cycle
28 return false;
29 }
30};
31
1// Function to detect whether a singly-linked list has a cycle.
2// This uses Floyd's Tortoise and Hare algorithm.
3function hasCycle(head: ListNode | null): boolean {
4 // Initialize two pointers, 'slowPointer' and 'fastPointer' at the head of the list.
5 let slowPointer = head;
6 let fastPointer = head;
7
8 // Traverse the list with both pointers.
9 while (fastPointer !== null && fastPointer.next !== null) {
10 // Move 'slowPointer' one step.
11 slowPointer = slowPointer.next;
12 // Move 'fastPointer' two steps.
13 fastPointer = fastPointer.next.next;
14
15 // If 'slowPointer' and 'fastPointer' meet, a cycle is detected.
16 if (slowPointer === fastPointer) {
17 return true;
18 }
19 }
20
21 // If 'fastPointer' reaches the end of the list, no cycle is present.
22 return false;
23}
24
Time and Space Complexity
The given Python code is using the Floyd's Tortoise and Hare algorithm to find a cycle in a linked list.
Time Complexity
The time complexity of the code is O(N)
, where N
is the number of nodes in the linked list. In the worst-case scenario, the fast pointer will meet the slow pointer in one pass through the list, if there is a cycle.
Space Complexity
The space complexity of the code is O(1)
. This is because the algorithm uses only two pointers, regardless of the size of the linked list, which means it only requires a constant amount of extra space.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
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
Want a Structured Path to Master System Design Too? Donāt Miss This!