Linked List Cycle

Easylinked-listtwo-pointers
Category: Linked List
Companies that ask this question:
AmazonMicrosoftFacebookGoogleYahoo
LeetCode →NeetCode →

Approach

Linked List Cycle

Problem Statement

Given the head of a linked list, determine if the linked list has a cycle in it.

A cycle exists if there is a node in the list that can be reached again by continuously following the next pointer.

Return true if there is a cycle in the linked list. Otherwise, return false.

Approach: Floyd's Cycle Detection Algorithm (Tortoise and Hare)

The optimal solution uses two pointers moving at different speeds to detect a cycle.

Algorithm

  1. Initialize Two Pointers:

    • slow pointer moves one step at a time
    • fast pointer moves two steps at a time

  2. Traverse the List:

    • Move slow forward by 1 node
    • Move fast forward by 2 nodes
    • If they ever meet, there's a cycle

  3. Return Result:

    • If fast reaches the end (null), there's no cycle
    • If slow and fast meet, there's a cycle

Why This Works

No Cycle: If there's no cycle, fast will eventually reach the end of the list.

With Cycle: If there's a cycle:

  • Both pointers will eventually enter the cycle
  • Once in the cycle, fast will catch up to slow
  • Think of it like two runners on a circular track - the faster runner will eventually lap the slower one

Time Complexity

  • Time: O(n) where n is the number of nodes
    • Without cycle: fast reaches end in n/2 steps
    • With cycle: fast catches slow within n steps
  • Space: O(1) - only two pointers

Example Walkthrough

For a list with cycle: 3 → 2 → 0 → -4 → (back to 2)

  1. Step 0: slow=3, fast=3
  2. Step 1: slow=2, fast=0
  3. Step 2: slow=0, fast=-4
  4. Step 3: slow=-4, fast=0
  5. Step 4: slow=2, fast=-4
  6. Step 5: slow=0, fast=0 → Cycle detected!

Alternative Approaches

1. Hash Set

  • Store visited nodes in a hash set
  • If we visit a node already in the set, there's a cycle
  • Time: O(n), Space: O(n)
  • Simple but uses extra space

2. Modify List Nodes

  • Mark visited nodes by modifying their value or creating a new field
  • Not recommended as it modifies the input
  • Time: O(n), Space: O(1)

Key Insights

  1. The two-pointer technique is elegant and space-efficient
  2. The relative speed difference (1 vs 2) is sufficient to detect any cycle
  3. This pattern applies to many cycle detection problems
  4. No need to track visited nodes explicitly

Solution

java
1/**
2 * Linked List Cycle - Floyd's Cycle Detection Algorithm
3 *
4 * Time Complexity: O(n)
5 * Space Complexity: O(1)
6 */
7
8class ListNode {
9    int val;
10    ListNode next;
11    ListNode(int x) {
12        val = x;
13        next = null;
14    }
15}
16
17public class Solution {
18    public boolean hasCycle(ListNode head) {
19        // Edge case: empty list or single node
20        if (head == null || head.next == null) {
21            return false;
22        }
23
24        // Initialize two pointers
25        ListNode slow = head;
26        ListNode fast = head;
27
28        // Traverse the list
29        while (fast != null && fast.next != null) {
30            // Move slow by 1 step
31            slow = slow.next;
32            // Move fast by 2 steps
33            fast = fast.next.next;
34
35            // If they meet, there's a cycle
36            if (slow == fast) {
37                return true;
38            }
39        }
40
41        // Fast reached the end, no cycle
42        return false;
43    }
44}
45
46// Alternative: Hash Set Approach
47class Solution2 {
48    public boolean hasCycle(ListNode head) {
49        Set<ListNode> visited = new HashSet<>();
50        ListNode current = head;
51
52        while (current != null) {
53            // If we've seen this node before, there's a cycle
54            if (visited.contains(current)) {
55                return true;
56            }
57
58            // Mark node as visited
59            visited.add(current);
60            current = current.next;
61        }
62
63        // Reached end, no cycle
64        return false;
65    }
66}
67
Loading visualizer...