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 using slow.next.
The fast pointer is moved by two nodes at a time using fast.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 a null next pointer and the loop will end, hence the condition while fast and fast.next: in our loop.
If there is a cycle, fast will eventually meet slow 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 Evaluator

Example 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 node 1
- fast is at node 1
We then start iterating through the list:
- Move slow to the next node (2), move fast two nodes ahead (3).
On the next iteration:
- Move slow to 3, move fast to 5.
Next iteration:
- Move slow to 4, move fast two nodes ahead but because of the cycle, it lands on 2.
On the following iteration:
- Move slow to 5, fast moves to 4.

At this point the loop continues:

slow moves to node 2 (following the cycle) and fast to node 3.
Next, slow moves to 3 and fast jumps two steps, landing on 5 again.
Finally, slow goes to 4 and fast which is at 5 now makes a two-step jump and lands on 4, meeting the slow 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don’t know