Two-Pointer Techniques - Learning Module

Loading content...

0/276

Finding the Middle Element

The Divide and Conquer Foundation

Consider one of the most important algorithmic paradigms: divide and conquer. To divide, you need to find the middle. In arrays, this is trivial—just calculate (low + high) / 2. But linked lists present a unique challenge: there's no random access, no length property eagerly available.

How do you find the middle of a linked list without knowing its length? How do you do it in a single pass? And how do you handle the subtle difference between 'first middle' and 'second middle' for even-length lists?

These questions matter because finding the middle is fundamental to:

Merge sort on linked lists (dividing the list for recursive sorting)
Balanced BST construction (the middle becomes the root)
Palindrome checking (compare first half with reversed second half)
Many interview problems where 'middle' is part of the solution

The slow and fast pointer technique provides elegant, O(n) time and O(1) space solutions to all these scenarios.

What You Will Learn

By the end of this page, you will master multiple variants of middle-finding, understand when to use each variant, and see how small implementation changes produce different results. You'll also learn how this technique enables efficient divide-and-conquer algorithms on linked lists.

The Problem Space: What Is 'Middle'?

Before diving into solutions, we must precisely define the problem. 'Middle' is ambiguous when the list has an even number of nodes.

Odd-length lists (n = 2k + 1):

Nodes: 1, 2, 3, 4, 5 (n=5, k=2)
Middle is node 3 (index 2)
Unambiguous: there's exactly one node with equal nodes on both sides

Even-length lists (n = 2k):

Nodes: 1, 2, 3, 4 (n=4, k=2)
Two 'middle' candidates: node 2 (left-middle) or node 3 (right-middle)
We must choose based on the application

Middle Node Definitions
List Length	Nodes	Left-Middle (Lower)	Right-Middle (Upper)
n=1	1	1	1
n=2	1 → 2	1	2
n=3	1 → 2 → 3	2	2
n=4	1 → 2 → 3 → 4	2	3
n=5	1 → 2 → 3 → 4 → 5	3	3
n=6	1 → 2 → 3 → 4 → 5 → 6	3	4

Mathematical Definition:

Left-middle: node at index ⌊(n-1)/2⌋ (0-indexed)
Right-middle: node at index ⌈(n-1)/2⌉ or equivalently ⌊n/2⌋

For odd n, these are equal. For even n, left-middle is the smaller index.

Which to use?

Merge sort: Often uses left-middle for the first half's last node, then splits
Palindrome check: Left-middle works well for reversing the second half
BST construction: Either works, but consistency matters
LeetCode 'Middle of Linked List': Typically asks for right-middle for even-length

Interview Clarification

Always clarify which middle is expected in interviews. The classic problem 'Middle of the Linked List' (LeetCode #876) asks for the second middle node when there are two. Other problems may need the first. A quick 'For even-length lists, do you want the first or second middle?' shows attention to detail.

Core Algorithm: Slow and Fast Pointers

The slow and fast pointer technique finds the middle in a single pass without counting nodes first. The key insight is simple:

When fast traverses the entire list at 2x speed, slow traverses half the list at 1x speed.

When fast reaches the end (null or last node), slow is at the middle.

The Standard Algorithm (Right-Middle for Even Length):

find_middle_right.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def find_middle_right(head: ListNode) -> ListNode:
    """
    Find the middle node of a linked list.
    For even-length lists, returns the SECOND (right) middle.
    
    Example:
        1 → 2 → 3 → 4 → 5         returns node 3
        1 → 2 → 3 → 4             returns node 3 (second middle)
    
    Time: O(n)
    Space: O(1)
    """
    if not head:
        return None
    
    slow = head
    fast = head
    
    # Continue while fast can move forward
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow
 
 
# Trace for even list [1, 2, 3, 4]:
# Step 0: slow=1, fast=1
# Step 1: slow=2, fast=3
# Step 2: slow=3, fast=null (after 4)
# Result: Node 3 (right-middle) ✓
 
# Trace for odd list [1, 2, 3, 4, 5]:
# Step 0: slow=1, fast=1
# Step 1: slow=2, fast=3
# Step 2: slow=3, fast=5
# Step 3: (fast.next is null, loop ends)
# Result: Node 3 (exact middle) ✓

Why This Works (Right-Middle):

Let's trace the math for a list of length n:

Fast starts at position 0, moves 2 per step
After k steps, fast is at position 2k
Fast stops when 2k ≥ n-1 (reaching or passing the last node)
Minimum k satisfying this: k = ⌈(n-1)/2⌉
At this k, slow is at position k = ⌈(n-1)/2⌉

For n=4: k = ⌈3/2⌉ = 2, so slow at position 2 (node 3, 0-indexed) For n=5: k = ⌈4/2⌉ = 2, so slow at position 2 (node 3, exact middle)

Memory Aid

For right-middle: 'fast AND fast.next' in the while condition. The AND means we keep going until fast is at the last node or beyond. This extra step pushes slow to the right-middle for even lists.

Left-Middle Variant

To get the left-middle (first middle node for even-length lists), we need a small but crucial modification: start fast one position ahead of slow.

This offset causes fast to 'finish' one step earlier, leaving slow one position to the left of where it would otherwise be.

find_middle_left.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def find_middle_left(head: ListNode) -> ListNode:
    """
    Find the middle node of a linked list.
    For even-length lists, returns the FIRST (left) middle.
    
    Example:
        1 → 2 → 3 → 4 → 5         returns node 3
        1 → 2 → 3 → 4             returns node 2 (first middle)
    
    Time: O(n)
    Space: O(1)
    """
    if not head:
        return None
    
    slow = head
    fast = head.next  # Fast starts one ahead!
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow
 
 
# Trace for even list [1, 2, 3, 4]:
# Step 0: slow=1, fast=2
# Step 1: slow=2, fast=4
# Step 2: (fast.next is null, loop ends)
# Result: Node 2 (left-middle) ✓
 
# Trace for odd list [1, 2, 3, 4, 5]:
# Step 0: slow=1, fast=2
# Step 1: slow=2, fast=4
# Step 2: slow=3, fast=null (after 5)
# Result: Node 3 (exact middle) ✓

Right-Middle (Standard)

•slow = head; fast = head
•Loop: while fast AND fast.next
•Returns second middle for even lists
•Used by LeetCode #876
•Good when you want 'at least half' traversed

Left-Middle (Offset Start)

•slow = head; fast = head.next
•Loop: while fast AND fast.next
•Returns first middle for even lists
•Good for splitting lists at 'first half end'
•Common in merge sort implementations

Why the Difference Matters

For merge sort, we split [1,2,3,4] into [1,2] and [3,4]. The left-middle (node 2) is the last node of the first half—perfect for cutting the list. Using right-middle would give [1,2,3] and [4], an unbalanced split.

Getting the Node Before Middle

Many operations require the node before the middle—for example, to split a list or delete the middle node. We need to set prev.next = middle.next to remove middle, which requires access to prev.

Approach 1: Track Previous Explicitly

find_before_middle.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def find_before_middle(head: ListNode) -> ListNode:
    """
    Find the node BEFORE the middle node.
    Useful for list splitting and middle deletion.
    
    Returns:
        The node whose .next is the middle node
        Returns None if list has fewer than 2 nodes
    """
    if not head or not head.next:
        return None
    
    prev = None
    slow = head
    fast = head
    
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    
    return prev  # prev.next == slow (the middle)
 
 
def delete_middle_node(head: ListNode) -> ListNode:
    """
    Delete the middle node from the list.
    
    For [1,2,3,4,5], removes 3 → [1,2,4,5]
    For [1,2,3,4], removes 3 → [1,2,4]
    
    Time: O(n)
    Space: O(1)
    """
    if not head or not head.next:
        return None  # 0 or 1 node → empty after deletion
    
    if not head.next.next:
        # Exactly 2 nodes: remove the second one
        head.next = None
        return head
    
    # Find node before middle
    prev = None
    slow = head
    fast = head
    
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    
    # Skip over the middle node
    prev.next = slow.next
    
    return head

Approach 2: Adjust Fast Starting Position

An alternative approach that doesn't need an explicit prev variable—instead, we make slow lag one node behind where we want it:

approach_2_offset.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def split_list_at_middle(head: ListNode) -> tuple[ListNode, ListNode]:
    """
    Split a linked list into two halves.
    
    For [1,2,3,4,5] → ([1,2], [3,4,5])
    For [1,2,3,4] → ([1,2], [3,4])
    
    Returns:
        Tuple of (first_half_head, second_half_head)
    """
    if not head or not head.next:
        return (head, None)
    
    # We want slow to stop at the LAST node of first half
    # So we start fast even further ahead
    slow = head
    fast = head.next.next  # Two ahead for left-biased split
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # slow is now the last node of first half
    second_half = slow.next
    slow.next = None  # Cut the list
    
    return (head, second_half)
 
 
# Example trace for [1,2,3,4,5]:
# Initial: slow=1, fast=3
# Step 1: slow=2, fast=5
# Step 2: fast.next is null, stop
# slow=2, slow.next=3
# Split: [1,2] and [3,4,5] ✓

Choosing the Approach

Tracking prev explicitly is clearer and less error-prone. Adjusting fast's start is more elegant but requires careful reasoning about edge cases. Use whichever you find easier to verify correct.

Applications in Divide and Conquer

Middle-finding is essential for divide-and-conquer algorithms on linked lists. Let's explore the two most important applications: Merge Sort and Balanced BST Construction.

1. Merge Sort on Linked Lists

Merge sort for linked lists has significant advantages over arrays:

Splitting at the middle is O(n), not O(1), but...
Merging is O(n) with O(1) extra space (just pointer rewiring)
Overall: O(n log n) time, O(log n) stack space

The algorithm:

Find the middle and split the list
Recursively sort both halves
Merge the sorted halves

merge_sort_linked_list.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def merge_sort(head: ListNode) -> ListNode:
    """
    Sort a linked list using merge sort.
    
    Time: O(n log n)
    Space: O(log n) for recursion stack
    """
    # Base case: empty or single node
    if not head or not head.next:
        return head
    
    # Split the list at the middle
    left_end = get_end_of_first_half(head)
    right_start = left_end.next
    left_end.next = None  # Cut the connection
    
    # Recursively sort both halves
    left_sorted = merge_sort(head)
    right_sorted = merge_sort(right_start)
    
    # Merge sorted halves
    return merge(left_sorted, right_sorted)
 
 
def get_end_of_first_half(head: ListNode) -> ListNode:
    """Get the last node of the first half (for splitting)."""
    slow = head
    fast = head.next  # Offset for left-biased middle
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow  # Last node of first half
 
 
def merge(l1: ListNode, l2: ListNode) -> ListNode:
    """Merge two sorted linked lists."""
    dummy = ListNode(0)
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # Attach remaining nodes
    current.next = l1 if l1 else l2
    
    return dummy.next

2. Building a Balanced BST from a Sorted Linked List

Given a sorted linked list, we can construct a height-balanced BST where each node's left and right subtrees differ in height by at most 1. The middle element becomes the root, recursively:

Find the middle of the current range
Make it the root
Recursively build left subtree from elements before middle
Recursively build right subtree from elements after middle

sorted_list_to_bst.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def sorted_list_to_bst(head: ListNode) -> TreeNode:
    """
    Convert a sorted linked list to a height-balanced BST.
    
    The middle element becomes the root.
    Elements before it form the left subtree.
    Elements after it form the right subtree.
    
    Time: O(n log n) - finding middle at each level
    Space: O(log n) - recursion depth
    """
    if not head:
        return None
    
    if not head.next:
        return TreeNode(head.val)
    
    # Find the middle and the node before it
    prev = None
    slow = head
    fast = head
    
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
    
    # slow is the middle (will be root)
    # prev is the end of left half
    
    # Cut the list
    if prev:
        prev.next = None
    
    # Create root from middle
    root = TreeNode(slow.val)
    
    # Recursively build left subtree (if left half exists)
    if prev:  # head to prev forms left half
        root.left = sorted_list_to_bst(head)
    
    # Recursively build right subtree
    root.right = sorted_list_to_bst(slow.next)
    
    return root

Optimized BST Construction: O(n) Time

There's an O(n) approach that simulates inorder traversal: first count nodes, then build the tree bottom-up, advancing through the list as you create leaf nodes. This eliminates repeated middle-finding but is more complex to implement correctly.

Palindrome Detection in Linked Lists

A classic application of middle-finding: check if a linked list is a palindrome. The values should read the same forward and backward.

The Strategy:

Find the middle of the list
Reverse the second half
Compare the first half with the reversed second half
(Optional) Restore the list by reversing the second half again

This achieves O(n) time and O(1) space—optimal for this problem.

palindrome_linked_list.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def is_palindrome(head: ListNode) -> bool:
    """
    Check if a linked list is a palindrome.
    
    Uses middle-finding and reversal for O(1) space.
    
    Examples:
        1 → 2 → 2 → 1           → True
        1 → 2 → 3 → 2 → 1       → True
        1 → 2 → 3               → False
    
    Time: O(n)
    Space: O(1)
    """
    if not head or not head.next:
        return True
    
    # Step 1: Find the end of first half (and middle)
    slow = head
    fast = head
    
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # slow is now at the end of first half
    # slow.next is the start of second half
    
    # Step 2: Reverse the second half
    second_half_start = reverse_list(slow.next)
    
    # Step 3: Compare both halves
    first_half = head
    second_half = second_half_start
    is_palindrome_result = True
    
    while second_half:  # Second half is same length or shorter
        if first_half.val != second_half.val:
            is_palindrome_result = False
            break
        first_half = first_half.next
        second_half = second_half.next
    
    # Step 4: Restore the list (optional but good practice)
    slow.next = reverse_list(second_half_start)
    
    return is_palindrome_result
 
 
def reverse_list(head: ListNode) -> ListNode:
    """Reverse a linked list in place."""
    prev = None
    current = head
    
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    return prev

Why Restore the List?

Restoring the list after checking isn't strictly necessary if you 'own' the data. However, in production code or when the list might be used later, it's good practice. It prevents subtle bugs where other code expects the original structure.

Finding the kth Node from the End

An elegant extension of the two-pointer technique: instead of slow/fast at 2:1 speed, use two pointers with a fixed offset. One pointer leads by k nodes; when it reaches the end, the trailing pointer is k nodes from the end.

Why This Works:

Distance from end to trailing pointer = Distance from leader to end = k
Leader at null means leader has 'passed' the end by 0 steps
So trailing is exactly k steps from null = kth from end

kth_from_end.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
def find_kth_from_end(head: ListNode, k: int) -> ListNode:
    """
    Find the kth node from the end of the list.
    
    k=1 returns the last node
    k=2 returns the second-to-last node
    etc.
    
    Time: O(n)
    Space: O(1)
    
    Returns:
        The kth node from the end, or None if k > length
    """
    if not head or k <= 0:
        return None
    
    leader = head
    trailer = head
    
    # Move leader k nodes ahead
    for _ in range(k):
        if not leader:
            return None  # k is larger than list length
        leader = leader.next
    
    # Move both until leader reaches the end
    while leader:
        leader = leader.next
        trailer = trailer.next
    
    return trailer  # trailer is k nodes from the end
 
 
def remove_kth_from_end(head: ListNode, k: int) -> ListNode:
    """
    Remove the kth node from the end of the list.
    
    Uses a dummy node to handle edge cases cleanly.
    
    Time: O(n)
    Space: O(1)
    """
    # Dummy node simplifies edge cases (removing head)
    dummy = ListNode(0)
    dummy.next = head
    
    leader = dummy
    trailer = dummy
    
    # Move leader k+1 nodes ahead
    # So trailer will be one BEFORE the node to remove
    for _ in range(k + 1):
        if not leader:
            return head  # k > length, nothing to remove
        leader = leader.next
    
    # Move both until leader reaches null
    while leader:
        leader = leader.next
        trailer = trailer.next
    
    # trailer.next is the node to remove
    trailer.next = trailer.next.next
    
    return dummy.next
 
 
# Example: Remove 2nd from end of [1,2,3,4,5]
# After k+1=3 moves: leader at node 4, trailer at dummy
# Move together until leader=null:
#   leader=5, trailer=1
#   leader=null, trailer=2
# trailer.next = 3 (the 2nd from end), remove it
# Result: [1,2,4,5] ✓

Edge Case: Removing the Head

If k equals the list length, you're removing the head. The dummy node pattern handles this elegantly: dummy.next becomes the new head (head.next), and we return dummy.next. Without a dummy, you'd need special-case logic.

The Fixed-Offset Pattern

This is a generalization of slow/fast:

Problem	Pointer 1	Pointer 2	Relationship
Find middle	slow (1x speed)	fast (2x speed)	Speed ratio
Find kth from end	trailer	leader (k ahead)	Fixed offset
Detect cycle	slow (1x)	fast (2x)	Speed ratio

Both speed-ratio and fixed-offset are two-pointer techniques, just with different invariants.

Edge Cases and Testing

Middle-finding algorithms must handle several edge cases correctly. Here's a comprehensive test strategy:

Critical Edge Cases for Middle-Finding
Case	Input	Expected (Right)	Expected (Left)
Empty list	None	None	None
Single node	1	1	1
Two nodes	1 → 2	2	1
Three nodes	1 → 2 → 3	2	2
Four nodes	1 → 2 → 3 → 4	3	2
Five nodes	1 → 2 → 3 → 4 → 5	3	3
All same value	5 → 5 → 5 → 5	5 (3rd)	5 (2nd)

middle_finding_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def test_middle_finding():
    """Comprehensive test suite for middle-finding algorithms."""
    
    # Helper to create list from array
    def create_list(values):
        if not values:
            return None
        head = ListNode(values[0])
        current = head
        for val in values[1:]:
            current.next = ListNode(val)
            current = current.next
        return head
    
    # Test find_middle_right (second middle for even)
    def test_right_middle():
        # Empty
        assert find_middle_right(None) is None
        
        # Single node
        single = create_list([1])
        assert find_middle_right(single).val == 1
        
        # Two nodes → should return second
        two = create_list([1, 2])
        assert find_middle_right(two).val == 2
        
        # Three nodes → exact middle
        three = create_list([1, 2, 3])
        assert find_middle_right(three).val == 2
        
        # Four nodes → second middle
        four = create_list([1, 2, 3, 4])
        assert find_middle_right(four).val == 3
        
        # Five nodes → exact middle
        five = create_list([1, 2, 3, 4, 5])
        assert find_middle_right(five).val == 3
        
        print("Right-middle tests passed!")
    
    # Test find_middle_left (first middle for even)
    def test_left_middle():
        # Two nodes → should return first
        two = create_list([1, 2])
        assert find_middle_left(two).val == 1
        
        # Four nodes → first middle
        four = create_list([1, 2, 3, 4])
        assert find_middle_left(four).val == 2
        
        # Six nodes → first middle (node 3)
        six = create_list([1, 2, 3, 4, 5, 6])
        assert find_middle_left(six).val == 3
        
        print("Left-middle tests passed!")
    
    test_right_middle()
    test_left_middle()
    print("All middle-finding tests passed!")

Testing Strategy

Always test with odd lengths (1, 3, 5), even lengths (2, 4, 6), and boundary cases (0, 1, 2). The behavior at length 2 often reveals off-by-one errors. Test both the return value and that the original list isn't corrupted (unless modification is intended).

Summary: Mastering Middle-Finding

We've explored middle-finding in depth, from basic algorithms to real-world applications. Let's consolidate the key insights:

Key Takeaways

•'Middle' is ambiguous for even-length lists — Clarify whether you need left-middle or right-middle before implementing.
•Right-middle: both pointers start at head — while fast and fast.next. Standard for LeetCode problems.
•Left-middle: fast starts one ahead — fast = head.next. Better for list splitting in merge sort.
•Track prev for node-before-middle — Essential for deletion and splitting operations.
•Merge sort uses middle-finding for divide step — Combined with O(1) space merging, very efficient for linked lists.
•Palindrome detection combines middle + reversal — O(n) time, O(1) space palindrome check.
•kth from end uses fixed offset, not speed ratio — Different flavor of two-pointer: one leads by k nodes.

What's Next

In the final page of this module, we'll explore detecting the intersection of two linked lists—another elegant application of two-pointer techniques. You'll learn how to find where two lists merge, handling the complexity of different list lengths, all in O(n) time and O(1) space.

The middle-finding skills you've developed here provide the conceptual foundation: using pointer positioning to extract structural information from linked lists without extra space.

Page Complete

You now have complete mastery of middle-finding in linked lists. You understand both variants, can adapt the technique for different applications, and know how to combine it with other algorithms for powerful results like O(n) palindrome checking and O(n log n) merge sort.