DSA sheet · Linked List · Fast & slow pointer pattern

Linked List Cycle

This is the second problem of the fast and slow pointer pattern (the first one was the middle of the list). The question is: does the list loop back on itself somewhere? The teacher first solves it the natural way, by remembering every node we have seen in a hash set. That is already O(n) time, but it costs O(n) extra space. Then she removes the set completely with two runners going at different speeds on the same track. This "two runners on a circle" picture is the base of the next problem too (finding where the cycle starts), so learn it well here.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: remember visited nodes in a hash set
• Part B · Optimal: fast and slow pointers (Floyd's cycle check)
• Part C · Revision page

Part 0 · Before starting

What is a linked list?

A linked list is a chain of small boxes called nodes. Each node holds two things: a value (val) and a pointer to the next node (next). The last node's next is None, which means "the chain ends here".

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val       # the number stored in this box
        self.next = next     # the next box, or None at the end

[1] → [2] → [3] → [4] → None
 ↑
head

• head: the first node. It is the only thing we are given. From it we can reach every other node by following next.
• Walking the list: keep a pointer curr, start it at head, and do curr = curr.next again and again until curr becomes None.
• No index access: an array lets you jump to a[5] straight away. A list doesn't. To reach position i you must walk i steps from the head, so reaching a position costs O(n).
• Don't move head itself: the teacher always makes a copy (an "alias") such as curr = head and moves the copy. If you move head, you lose the start of the list.
• Save next before changing a pointer: if you overwrite node.next, the rest of the chain is lost unless you saved it first. (In this problem we only read pointers and never change one, so this rule doesn't bite here. It matters a lot in the reversal problems.)

What is a cycle?

Normally the last node points to None. In a list with a cycle, some node's next points back to an earlier node. Then there is no end: if you keep walking you go round and round forever.

[1] → [2] → [3] → [4] → [5] → [6]
       ↑                         │
       └─────────────────────────┘     (6.next is node 2, not None)

The fast and slow pointer tool

Two pointers start at the head. slow moves 1 node per step (slow = slow.next). fast moves 2 nodes per step (fast = fast.next.next). Because fast goes at double speed, at any moment slow has covered half the distance fast has covered. That is why, in the previous problem, slow ends at the middle when fast reaches the end.

• Odd length (e.g. 5 nodes): fast lands exactly on the last node, so fast.next is None → stop.
• Even length (e.g. 4 nodes): fast jumps past the last node and becomes None → stop.
• So the loop needs both checks: while fast and fast.next. The first protects against the even case, the second against the odd case (and makes fast.next.next safe).

Part A · Brute force: remember visited nodes in a hash set

LeetCode 141

1The question in simple words

You get the head of a linked list. Return True if the list has a cycle (some node can be reached again by following next), and False if the list ends at None.

[1] → [2] → [3] → [4] → [5] → [6]
       ↑                         │
       └─────────────────────────┘

[1] → [2] → [3] → [4] → None

On LeetCode you also see a number pos in the examples. It only tells the judge where the last node links back to. Your function never receives it; you only get head.

2What the constraints tell us

• Number of nodes: 0 to 10⁴ → 0 is allowed, so head can be None. An empty list has no cycle, so the answer is False, and the code must not crash.
• n is up to 10⁴, so even O(n²) would technically pass. But the teacher reminds us: in linked list problems you will rarely write O(n²). Almost everything is O(n). So "optimal" here means saving space, not time.

3Intuition: tick off every node you visit

Imagine walking through the list and putting a tick mark on every node you pass: 1 ✓, 2 ✓, 3 ✓, 4 ✓, 5 ✓, 6 ✓… and then you arrive at 2 again. It already has a tick! The only way to reach a ticked node again is to have gone round a loop. So "I've been here before" means there is a cycle.

If there is no loop, you never meet a ticked node. You simply fall off the end into None.

4Building the logic from examples

Where do we keep the ticks? A hash set

We need to ask "have I seen this before?" quickly. A Python set answers that in O(1) on average. So we keep a set called seen.

Store the node, not the value

The teacher asks: do we put the values in the set, or the nodes? Look at this list:

[1] → [2] → [2] → None        (two different nodes that both hold 2)

• Storing values: we add 1, then 2. At the third node, the value 2 is already in the set, so we'd say "cycle!" Wrong. There is no cycle; it's just two nodes with the same number.
• Storing nodes: the two 2-boxes are different objects (different addresses in memory), so the set treats them as different. No false alarm. Correct.

The check, the add, the move: in this order

1. Is curr already in seen? → yes means we came back → return True.
2. Otherwise add curr to the set, so it can be recognised next time.
3. Move on: curr = curr.next.

When does the loop stop? At None

If there is a cycle, the check in step 1 eventually fires and returns. But if there is no cycle, that check never fires. Without another way out we'd be stuck. The teacher's reasoning: a list without a cycle is a straight line, so it must end in None. When curr reaches None, we know there's no cycle.

5Approach steps

1. Make an empty set seen and a pointer curr = head.
2. While curr is not None: if curr is in seen → return True.
3. Otherwise add curr to seen and move curr = curr.next.
4. If the loop ends (we hit None) → return False.

6Code (Python)

class Solution:
    def hasCycle(self, head):
        seen = set()               # nodes we have already visited
        curr = head                # alias, so head stays untouched
        while curr is not None:
            if curr in seen:       # been here before -> loop
                return True
            seen.add(curr)         # tick this node
            curr = curr.next       # walk one step
        return False               # reached None -> straight list

7Code line by line

8Dry run

List: 1 → 2 → 3 → 4 → 5 → 6 → back to 2.

step 7:
[1] → [2] → [3] → [4] → [5] → [6]
       ↑                         │
       └─────────────────────────┘
       curr   (node 2 is already ticked → True)

Without a cycle, e.g. 1 → 2 → 3 → None: we tick 1, 2, 3, then curr becomes None, the loop ends, and we return False.

9Complexity & remember

• Time O(n): each node is visited once; with a cycle we visit each node once and then one more step to the repeated node.
• Space O(n): the set can hold every node.

The time is already as good as it gets for linked lists. The only thing to improve is the extra set. The interviewer will ask: "can you do it without extra space?"

Part B · Optimal: fast and slow pointers (Floyd's cycle check)

1The question (same as Part A)

Same input and output. New goal: O(1) extra space, so no set, just a couple of pointers.

2What the constraints tell us

• Head can be None (0 nodes). Our loop condition while fast and fast.next is False straight away, so we return False. No extra check needed.
• One node with no cycle: fast.next is None → return False. One node pointing to itself: handled by the loop (see the dry run of the edge cases).

3Intuition: two runners on a track

The teacher's picture: two people start a race at the same point. One runs at double the speed of the other.

• If the track is a straight line (no cycle), the fast runner simply reaches the finish line first. They never meet again. In the list, that "finish line" is None: fast or fast.next becomes None.
• If the track is a circle (a cycle), the fast runner goes round and comes up behind the slow runner, then catches them. Two people going round the same loop at different speeds must collide at some point.

So: if slow and fast ever stand on the same node → cycle → True. If fast reaches the end → no cycle → False.

4Building the logic from examples

Start both at head

slow = head, fast = head. Same starting point, like the race.

The loop condition: same as the middle-of-list problem

Fast is the one that runs ahead, so fast is the one that would hit the end. As we saw in Part 0, for an even-length list fast becomes None, and for an odd-length list fast.next becomes None. Both must be checked:

Inside the loop: move, then compare

• slow = slow.next (one jump)
• fast = fast.next.next (two jumps)
• if slow is fast: return True

5Approach steps

1. Set slow = head and fast = head.
2. While fast and fast.next both exist: move slow 1 step and fast 2 steps.
3. If slow and fast are now the same node → return True.
4. If the loop ends → fast reached the end → return False.

6Code (Python)

class Solution:
    def hasCycle(self, head):
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next          # 1 jump
            fast = fast.next.next     # 2 jumps
            if slow is fast:          # the runners met -> loop
                return True
        return False                  # fast fell off the end

7Code line by line

8Dry run

The teacher's list: 1 → 2 → 3 → 4 → 5 → 6 → back to 2. The cycle is 2 → 3 → 4 → 5 → 6 → 2 (5 nodes).

after step 3 (fast has lapped round and is now behind slow):
[1] → [2] → [3] → [4] → [5] → [6]
       ↑            ↑            │
      fast         slow          │
       └─────────────────────────┘

after step 5 (they meet):
[1] → [2] → [3] → [4] → [5] → [6]
       ↑                         │
       └─────────────────────────┘
                              ↑
                          slow, fast  (both on node 6)

Notice at step 3 fast is "behind" slow on the loop (fast on 2, slow on 4; the gap from fast forward to slow is 2). Step 4 → gap 1. Step 5 → gap 0. That's Doubt 4 in action. The meeting node is 6. It is not where the cycle starts (that's 2). Finding the start is the next problem.

A no-cycle run: 1 → 2 → 3 → 4 → 5 → None

Edge cases

• Empty list: fast is None → loop never runs → False.
• One node, no cycle: fast.next is None → False.
• One node pointing to itself: slow = node.next = node, fast = node.next.next = node → same → True.
• Two nodes, 2 points back to 1: step 1: slow = 2, fast = 1 → 2 → 1 = 1. Not equal. Step 2: slow = 1, fast = 1 → True.

9Complexity & remember

• Time O(n): without a cycle, fast reaches the end in about n/2 steps. With a cycle, slow enters the loop within n steps, and after that fast closes the gap by 1 per step, so it catches up in fewer steps than the loop length. Linear either way.
• Space O(1): only two pointer variables, whatever the size of the list.

The teacher's tip: whenever a question is about a middle point or a meeting point, and two things moving at different speeds could find it, think of fast and slow pointers.

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values, pos=-1):
    """Build a list; if pos >= 0, the last node links back to node at index pos."""
    nodes = [ListNode(v) for v in values]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    if pos >= 0 and nodes:
        nodes[-1].next = nodes[pos]
    return nodes[0] if nodes else None

s = Solution()
print(s.hasCycle(build([1, 2, 3, 4, 5, 6], 1)))   # True
print(s.hasCycle(build([1, 2, 3, 4, 5])))          # False
print(s.hasCycle(build([1, 2, 2])))                # False (equal values, no loop)
print(s.hasCycle(build([7], 0)))                   # True  (points to itself)
print(s.hasCycle(None))                            # False

Based on this video: Linked List Cycle | Fast and Slow Pointer