DSA sheet · Linked List · Fast & slow pointer pattern

Middle of the Linked List

This is the first problem of a new pattern: fast and slow pointers, one of the most used tricks in linked list questions. The task is simple (find the middle node), so it's the perfect place to learn the trick. The teacher first solves it by counting the length and walking again, then shows how a pointer that moves twice as fast finds the middle in a single pass. She also works out the exact loop condition for odd and even lengths.

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 · Linked list basics + the fast/slow idea
Part A · Count the length, then walk half (brute force)
Part B · Fast and slow pointers (optimal)
Part C · Revision page

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of nodes. Each node holds a value (val) and a link to the next node (next). The last node's next is None.

given by LeetCode, don't write this in the solution

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

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

head points to the first node. We don't move head itself; we move helper pointers (aliases) such as curr, slow and fast.
Walking: curr = curr.next moves one node forward. Doing it until curr is None visits every node.
No index access: with an array of length n you'd just read index n/2. A linked list has no indices: reaching position i means walking i links, O(i). That is the whole difficulty of this problem.
Save next before changing a pointer: if you rewrite a .next, keep a pointer to the old next first, or that part of the list is lost. (This page only walks and never rewires, but the rule matters on most other pages.)

The fast and slow pointer tool

Two pointers start together at the head. Each round, slow moves 1 node and fast moves 2 nodes.

Why slow ends at the middle: after k rounds, slow has moved k nodes and fast has moved 2k. Fast has always covered twice slow's distance, so slow has always covered half of fast's. When fast reaches the end of the list, slow is halfway: the middle.
Odd vs even length: with an odd number of nodes, fast lands exactly on the last node (its next is None). With an even number, fast jumps past the end and becomes None. We must stop in both situations (worked out in Part B).
Why they would meet (for later pages): if a list has a cycle, fast never reaches None. Inside the loop, fast gains one node on slow every round, so the gap between them shrinks by 1 each round until it is 0 and they stand on the same node. That's how the next problems (Linked List Cycle I/II) use the same pair.

Part A · Count the length, then walk half

LeetCode 876 · Middle of the Linked List

1The question in simple words

Given the head of a list, return its middle node. If the list has two middle nodes (even length), return the second one.

Odd length: one middle

[1] → [2] → [3] → [4] → [5] → None
             ↑
           middle → return 3 → 4 → 5

Even length: two middles, return the 2nd

[1] → [2] → [3] → [4] → [5] → [6] → None
             ↑     ↑
          1st mid  2nd mid → return 4 → 5 → 6

We return the node, not the number. Returning node 4 hands back 4 → 5 → 6, because the nodes are linked.

2What the constraints tell us

Number of nodes: 1 to 100. At least one node, so head is never None. The size is tiny, so nothing can overflow and even a slow method would pass.
But the teacher's general point: in linked list problems we almost never need O(n²). Linear solutions are the norm, and the interesting question is how few passes we can make.

3Intuition: an array would be easy, so recreate what the array gives us

If this were an array of length n, we'd return the element at index n / 2. A list doesn't know its length and can't jump to an index. So we do it in two walks: one walk to count the nodes, a second walk to step exactly length // 2 times from the head.

4Building the logic from examples

Odd, length 5: 5 // 2 = 2 (5 / 2 = 2.5, and integer division drops the .5). Start at node 1, jump twice: 1 → 2 → 3. Node 3 is the middle. ✓
Even, length 4 (1 → 2 → 3 → 4): the middles are 2 and 3, and we want 3. 4 // 2 = 2 jumps: 1 → 2 → 3. ✓ The same rule automatically gives the second middle.
Even, length 6: 6 // 2 = 3 jumps: 1 → 2 → 3 → 4. ✓

Doubt: after counting, my pointer is at None. How do I walk again?
→ Restart it from head. That's why we counted with an alias curr and never moved head itself.

5Approach steps

Walk the list with curr, counting nodes into length.
Compute middle = length // 2.
Put curr back on head and move it middle times.
Return curr.

6Code (Python)

Middle of the list, count then walk

class Solution:
    def middleNode(self, head):
        length = 0
        curr = head
        while curr:                 # pass 1: count the nodes
            length += 1
            curr = curr.next

        middle = length // 2        # number of jumps from the head
        curr = head                 # restart from the head
        for _ in range(middle):     # pass 2: walk half way
            curr = curr.next
        return curr

7Code line by line

line	what it means
curr = head	An alias, so head stays on the first node.
while curr: length += 1 curr = curr.next	Count every node. When the loop ends, `curr` is None.
middle = length // 2	How many jumps from the head reach the middle (the second middle for even lengths).
curr = head	Back to the start for the second walk.
for _ in range(middle): curr = curr.next	Take exactly `middle` jumps.
return curr	The middle node (and the rest of the list hanging from it).

8Dry run

list	pass 1: length	middle = length // 2	pass 2 jumps	answer
1→2→3→4→5	5	2	1 → 2 → 3	node 3
1→2→3→4	4	2	1 → 2 → 3	node 3 (2nd middle)
1→2→3→4→5→6	6	3	1 → 2 → 3 → 4	node 4 (2nd middle)
7	1	0	no jumps	node 7

pass 2 on 1→2→3→4→5 (middle = 2):
[1] → [2] → [3] → [4] → [5] → None
 ↑                               start
       ↑                         after jump 1
             ↑                   after jump 2 → return [3]

9Complexity & remember

Time: n steps to count + n/2 steps to walk = 3n/2. That is still O(n), and with only 100 nodes LeetCode even reports it as fast.
But the teacher's rule of thumb: in linked lists, a solution that needs "n plus something" passes is usually the brute force. If you can do it in one pass, that's the optimised answer.
Space O(1): one pointer and one counter.

Remember the brute force Count → length // 2 → restart at head → jump that many times. Gives the 2nd middle for even lengths automatically. Two passes (3n/2).

Part B · Fast and slow pointers

1The question (same as Part A)

Return the middle node (the second middle for even lengths), but now in one pass, without counting the length first.

2What the constraints tell us

At least 1 node, so head exists and both pointers can start on it.
O(n) is the target. Part A was already O(n); here we cut it from 3n/2 steps to one walk of the fast pointer.

3Intuition: two runners, one twice as fast

Two runners start together. One runs at speed 1, the other at speed 2. When the fast one reaches the finish line, where is the slow one? Exactly halfway, because in the same time it covered half the distance. Replace "finish line" with "end of the list", and "halfway" is the middle node. No counting needed.

4Building the logic from examples

The teacher takes one odd and one even example and moves the pointers by hand.

Odd length: 1 → 2 → 3 → 4 → 5

start:     [1] → [2] → [3] → [4] → [5] → None
           s,f
round 1:   [1] → [2] → [3] → [4] → [5] → None
                  s     f
round 2:   [1] → [2] → [3] → [4] → [5] → None
                        s           f        f.next is None → stop

After round 2, fast is on the last node. It can't take two more steps (there's only None after it), and slow is already on 3, the middle. So here the stop signal is fast.next is None.

Even length: 1 → 2 → 3 → 4 → 5 → 6

start:     [1] → [2] → [3] → [4] → [5] → [6] → None
           s,f
round 1:          s     f
round 2:                s           f
round 3:                      s                 f = None → stop

After round 3, fast jumped from 5 over 6 to None, and slow is on 4, the second middle, which is exactly what the question wants. Here the stop signal is fast is None.

Doubt 1: which stop condition belongs to which length? It's easy to mix up.
→ Odd length: fast stops on the last node → fast.next is None. Even length: fast steps past the end → fast is None. (While explaining on the board, the teacher swapped these labels at one point; the pictures above show the correct pairing. The code needs both checks anyway, so it doesn't change the solution.)

Turning the two stop signals into a loop condition

Stop if fast is None or fast.next is None. So keep going while fast is not None and fast.next is not None. Inside the loop: slow = slow.next and fast = fast.next.next.

Doubt 2: why and, and why must fast be checked before fast.next?
→ In the even case, fast becomes None first. With and, Python sees fast is not None is False and stops checking at once. With or, a False first part makes Python go on and evaluate the second part, fast.next, which is "next of None" → crash. The same crash happens if you write the fast.next check first. So: and, and fast first.

Doubt 3: is fast.next.next safe inside the loop?
→ Yes. The loop only runs when fast.next exists, so fast.next.next is either a node or None, both fine to assign. And slow is always behind fast, so slow.next always exists.

Doubt 4 (extra, useful later): what if a problem wants the first middle for even lengths?
→ Use while fast.next and fast.next.next. Fast then stops one round earlier on even lengths, so slow stays on the first middle. Not needed here, but it comes up in problems like Palindrome Linked List and Sort List.

5Approach steps

Put both slow and fast on the head.
While fast and fast.next both exist: move slow one step, fast two steps.
When the loop stops, return slow.

6Code (Python)

Middle of the list, fast & slow

class Solution:
    def middleNode(self, head):
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next          # 1 step
            fast = fast.next.next     # 2 steps
        return slow

7Code line by line

line	what it means
slow = head fast = head	Both runners start at the same place.
while fast is not None and fast.next is not None:	Fast can still take two steps. Stops when fast is None (even length) or on the last node (odd length).
slow = slow.next	Slow moves 1 node.
fast = fast.next.next	Fast moves 2 nodes, so it always has covered twice slow's distance.
return slow	Fast reached the end, so slow is at the middle (the 2nd middle for even lengths).

8Dry run

list	round	slow	fast	check before next round	answer so far
1→2→3→4→5	start	[1]	[1]	fast ✓, fast.next ✓	—
	1	[2]	[3]	fast ✓, fast.next ✓	—
	2	[3]	[5]	fast.next is None → stop	[3]
1→2→3→4→5→6	start	[1]	[1]	✓ ✓	—
	1	[2]	[3]	✓ ✓	—
	2	[3]	[5]	✓ ✓	—
	3	[4]	None	fast is None → stop	[4]
1→2→3→4	start → 1	[1] → [2]	[1] → [3]	✓ ✓	—
1→2→3→4	2	[3]	None	fast is None → stop	[3]
7	start	[7]	[7]	fast.next is None → no rounds	[7]

Snapshots of the even example when the loop stops:

[1] → [2] → [3] → [4] → [5] → [6] → None
                   ↑                   ↑
                  slow                fast   → return [4] (4 → 5 → 6)

And of the odd example when the loop stops:

[1] → [2] → [3] → [4] → [5] → None
             ↑           ↑
            slow        fast (fast.next is None) → return [3]

9Complexity & remember

Time O(n): one walk. Fast reaches the end after about n/2 rounds, and slow does n/2 steps in those same rounds. Exactly O(n) in one pass, versus 3n/2 in Part A.
Space O(1): just two pointers.

Remember fast & slow Both start at head. while fast and fast.next: slow +1, fast +2. Return slow. Odd: fast ends on the last node. Even: fast ends on None, slow on the 2nd middle.

Part C · Revision page

	Count then walk	Fast & slow
passes	2 (count, then walk half)	1
steps	n + n/2 = 3n/2	about n (fast covers the list once)
time / space	O(n) / O(1)	O(n) / O(1)
even length gives	2nd middle (length // 2 jumps)	2nd middle (fast falls to None)
status	brute force	optimal, and the template for the whole pattern

length	where fast stops	which check fails	slow is on
odd (5)	last node	`fast.next is None`	the middle (3)
even (6)	None	`fast is None`	the 2nd middle (4)

If you remember only 5 lines 1. Lists have no index, so "length / 2" needs a counting pass first (3n/2 steps).
2. Fast moves 2, slow moves 1 → slow has always walked half of fast's distance.
3. Loop while fast and fast.next (and, fast checked first).
4. Odd: fast stops on the last node. Even: fast becomes None.
5. Return slow: the middle, or the 2nd middle for even lengths. O(n), O(1).

Mistakes to avoid ✗ or instead of and in the loop condition (None.next crash)
✗ checking fast.next before fast
✗ only checking fast.next (crashes on even lengths when fast is None)
✗ returning slow.val when the problem wants the node
✗ in the brute force, forgetting to reset curr to head before the second walk

test it yourself (paste under either solution above)

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

def build(vals):
    head = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head

s = Solution()
print(s.middleNode(build([1, 2, 3, 4, 5])).val)      # 3
print(s.middleNode(build([1, 2, 3, 4, 5, 6])).val)   # 4
print(s.middleNode(build([1, 2])).val)               # 2
print(s.middleNode(build([7])).val)                  # 7

Based on this video: Middle of the Linked List | Fast & Slow Pointer