Linked List Cycle

The problem

You are given the head of a singly linked list. Return true if the list has a cycle: some node’s next pointer leads back to a node seen earlier, so walking the list never ends. Return false if the walk reaches null.

In the examples, cycle_index is the index the last node links back to, or −1 for no cycle. It only describes the test. Your function gets just head.

Example 1

Input: head = [5, 2, 9, 4, 7, 1], cycle_index = 2

Output: true

The last node, 1, points back to 9. From there the walk goes round 9, 4, 7, 1 forever.

Example 2

Input: head = [6, 3], cycle_index = 0

Output: true

3 points back to 6, so the two nodes form a loop.

Example 3

Input: head = [8], cycle_index = -1

Output: false

One node that points to null. The walk ends.

Constraints

• 0 ≤ n ≤ 10,000, where n is the number of nodes
• −100,000 ≤ Node.val ≤ 100,000
• cycle_index is −1 or a valid index.

Clarifying questions

Can we tell a cycle by the values?

No. Values can repeat. We must compare the nodes themselves, by identity.

Can the list be empty?

Yes. An empty list has no cycle, so return false.

May we change the list, for example mark visited nodes?

Better not. The fast and slow pointers need no changes and no extra memory.

Do we need to find where the cycle starts?

No, only whether there is one. Finding the start is a follow-up problem.

Spot the pattern

We cannot count on reaching an end, and we want O(1) memory. Picture two runners on a track: the faster one laps the slower one only if the track is a loop. Two pointers that move at different speeds turn that into code. This is the fast and slow pointers pattern, a kind of two pointers.

Solutions

Hash setO(n), O(n) spaceFast and slowO(n), O(1) space

Show all

This problem has two approaches. Both are O(n) time, and the second one removes the extra memory.

Hash set O(n), O(n) space

The idea

Walk the list and put every node you pass into a set. Before adding a node, check if it is already there. If it is, you came back to it, so there is a cycle. If the walk reaches null, there is none.

The set stores the nodes themselves, not their values, because values can repeat.

Walkthrough

seen (nodes)

empty

1. seen = set()
2. node = head
3. while node:
4. if node in seen:
5. return True
6. seen.add(node)
7. node = node.next
8. return False

Walk the list and remember every node we pass in a set. Coming back to a remembered node means a cycle.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Hash set: remember every node we pass. Meeting one again means a cycle.
    // One pass, so O(n) time, but the set holds up to n nodes: O(n) memory.
    public boolean hasCycle(ListNode head) {
        // Store the nodes themselves, not values: values can repeat.
        java.util.Set<ListNode> seen = new java.util.HashSet<>();
        for (ListNode node = head; node != null; node = node.next) {
            // add returns false when the node is already there.
            if (!seen.add(node)) return true;
        }
        // We reached the end, so there is no loop.
        return false;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one set lookup, one set add and one pointer move. A set lookup and add take one step on average, so each run is 1 step. There is one loop.

   1. seen = set()
   2. node = head
   3. while node:
   4. if node in seen:
   5. return True
   6. seen.add(node)
   7. node = node.next
   8. return False

2. 2 Count the runs on Example 1

   Example 1 has 6 nodes. The walk adds all 6 to the set. On the 7th run it reaches 9 again and finds it in the set.

   7 runs.

   run	1	2	3	4	5	6	7
   node	5	2	9	4	7	1	9 again

3. 3 Write the count for any n

   Every node is added once. With a cycle, one more run finds the repeat. Without one, the walk stops at null:

   at most n + 1 runs

   Check it with Example 1: 6 + 1 = 7.

4. 4 Keep only the part that grows fastest

   Drop the + 1. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The set ends up holding every node, so n entries. The space is O(n).

   seen (up to n nodes)node

Fast and slow O(n), O(1) space

The idea

Start two pointers at the head. Each run, slow moves 1 node and fast moves 2.

• If the list has an end, fast reaches it first. Then return false.
• If the list has a cycle, both pointers end up going round it. Inside the loop, fast gains exactly one node on slow per run. So the gap between them shrinks by 1 each run, and it must reach 0. Then they stand on the same node: return true.

Fast cannot jump over slow. The gap shrinks by exactly 1, so it hits 0 before it could go below.

Why it never misses the answer: with no cycle, fast reaches null. With a cycle, the gap shrinks by 1 every run, so the two must meet.

Walkthrough

1. slow = fast = head
2. while fast and fast.next:
3. slow = slow.next
4. fast = fast.next.next
5. if slow is fast:
6. return True
7. return False

Both pointers start at the head. slow moves 1 node per run, fast moves 2.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Fast and slow pointers: in a loop, fast gains one node per run on slow,
    // so they must meet. O(n) time and O(1) memory.
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        // Check both: fast moves two nodes, so either one may be the end.
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // Same node, not same value. The gap shrank to 0, so they share a loop.
            if (slow == fast) return true;
        }
        // fast fell off the end, so the list has an end.
        return false;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run moves slow once, moves fast twice and compares them. That is 1 step. There is one loop. The question is how many runs it takes for them to meet.

   1. slow = fast = head
   2. while fast and fast.next:
   3. slow = slow.next
   4. fast = fast.next.next
   5. if slow is fast:
   6. return True
   7. return False

2. 2 Count the runs on Example 1

   Example 1: the loop has 4 nodes. After run 2, both pointers are in it and fast is 2 behind. Run 3 makes it 1, run 4 makes it 0, and they meet on 7.

   4 runs.

   	run 1	run 2	run 3	run 4
   slow	2	9	4	7
   fast	9	7	9	7
   gap	–	2	1	0

3. 3 Write the count for any n

   Say the part before the loop has t nodes and the loop has L nodes, so t + L = n. Slow enters the loop after t runs. At that moment fast is less than L nodes behind it, and the gap shrinks by 1 each run:

   at most t + L = n runs

   Without a cycle, fast falls off the end after about n / 2 runs. Check it with Example 1: t = 2 and L = 4, so at most 6 runs. It took 4.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. In both cases the count is at most n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps two pointers, slow and fast. That is fixed, for any n, so the space is O(1).

   slowfast

Common mistake

Checking only fast.next

The loop must check fast and fast.next before moving fast two steps. If fast itself is null, fast.next crashes. If fast.next is null, fast.next.next crashes. An even-length list with no cycle hits the first case.

Tested at the limits

2,000 random lists of 0 to 8 nodes, with repeated values, and about half of them with a loop back to a random node. The hash set and the fast and slow pointers gave the same answer every time.

Largest inputs	Result
10,000 nodes (the most allowed): with no loop, with the tail linking back to the head, and with the tail pointing to itself. Fast and slow.	Under 0.001 s each, and under 0.001 MB of extra memory: just the two pointers.
10,000 nodes, the same lists. Hash set.	Under 0.001 s, and about 0.6 MB of extra memory: the set holds every node, which is the O(n) space.