Common Linked List Patterns - Learning Module

Loading content...

0/279

Removing Nth Node from End

The Elegance of the Two-Pointer Gap

Here's a deceptively simple problem: Given a linked list, remove the nth node from the end and return the head.

At first glance, this seems to require knowing the list's length—after all, "nth from the end" implies you need to know where the end is. The naïve approach traverses twice: once to count nodes, once to find the target. But there's a beautiful one-pass solution using two pointers maintained at a fixed distance.

This pattern—creating a gap between two pointers—is one of the most elegant techniques in linked list manipulation. It transforms a two-pass problem into a one-pass solution, and it appears in many variations: finding the middle, detecting cycles, and more.

This page will take you from the basic two-pass approach through the optimized one-pass solution, covering all edge cases and building the intuition that makes this pattern feel natural.

What You Will Learn

By the end of this page, you will: (1) Understand the two-pass approach and why we can do better, (2) Master the one-pass two-pointer solution with a gap, (3) Handle all edge cases including removing the head, (4) Visualize why the gap technique works, (5) Recognize variations of this pattern in other problems.

The Problem Statement

Problem:

Given the head of a linked list, remove the nth node from the end of the list and return the head of the modified list.

Example 1:

Input:  1 → 2 → 3 → 4 → 5, n = 2
Output: 1 → 2 → 3 → 5
Explanation: The 2nd node from the end is 4.

Example 2:

Input:  1 → 2 → 3, n = 3
Output: 2 → 3
Explanation: The 3rd node from the end is 1 (the head).

Constraints:

The list has at least one node
1 ≤ n ≤ length of the list
The list is singly linked (no prev pointer)

Problem Requirements Summary
Aspect	Requirement
Input	Head of linked list, integer n
Output	Head of modified list after removal
Target	nth node from the END (1-indexed)
Time Goal	O(n) — traverse the list once
Space Goal	O(1) — constant extra space
Edge Case	When n equals list length (remove head)

The Challenge:

In a singly linked list, we can only traverse forward. To remove the nth node from the end, we seemingly need to know where the end is first. But the one-pass solution cleverly uses the relationship between two pointers to locate the target without explicit length calculation.

The Two-Pass Approach — Baseline Solution

Before optimizing, let's understand the straightforward two-pass approach. It's correct, easy to understand, and serves as a baseline:

Pass 1: Count the total number of nodes (call it length). Pass 2: The node to remove is at position length - n + 1 from the beginning. Traverse to node length - n and skip over the target.

remove_nth_two_pass.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
def remove_nth_from_end_two_pass(head: ListNode, n: int) -> ListNode:
    """
    Remove nth node from end using two passes.
    
    Time Complexity: O(L) where L is list length
    Space Complexity: O(1)
    
    Pass 1: Count nodes
    Pass 2: Remove at position (length - n)
    """
    # Pass 1: Count the length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    # Edge case: removing the head
    # If n == length, target is the first node
    if n == length:
        return head.next
    
    # Pass 2: Navigate to node before the target
    # Target is at position (length - n) from start (0-indexed)
    # We need to stop at position (length - n - 1)
    steps_to_prev = length - n - 1
    current = head
    
    for _ in range(steps_to_prev):
        current = current.next
    
    # 'current' is now the node before the target
    # Skip over the target
    current.next = current.next.next
    
    return head
 
 
# Trace example: Remove 2nd from end of [1,2,3,4,5]
# Pass 1: length = 5
# Target position from start: 5 - 2 = 3 (0-indexed: node 4)
# We need node at position 2 (node 3) to skip over node 4
# Steps to prev: 5 - 2 - 1 = 2
# After 2 steps from head: we're at node 3
# Set node3.next = node3.next.next (skip node 4)
# Result: 1 → 2 → 3 → 5

Two-Pass Trade-offs

The two-pass approach is perfectly valid and often easier to get right in interviews. It's O(L) time (two traversals) and O(1) space. The one-pass approach is also O(L) time but makes exactly one traversal. For very long lists where cache effects matter, one pass is better. For interviews, correctness matters more than micro-optimization.

The One-Pass Insight — The Gap Technique

The one-pass solution is built on a beautiful insight:

If we maintain two pointers with a gap of exactly n nodes between them, when the front pointer reaches the end, the back pointer is exactly at the nth node from the end.

Think about it:

If the front pointer is n steps ahead of the back pointer
And the front pointer just reached the end (null)
Then the back pointer is n steps from the end

To remove the nth node, we actually want to stop one node before it. So we maintain a gap of n nodes and use a dummy node to handle the edge case of removing the head.

The Gap Visualization

Picture a ruler with two marks: one at 0 and one at n. As you slide this ruler along the list, when the n-mark reaches the end, the 0-mark is at position (length - n). This is exactly the node before the one we want to remove.

Step-by-Step Algorithm:

Create a dummy node pointing to head (handles edge case of removing head)
Initialize both fast and slow at the dummy
Move fast forward by n+1 steps (creating a gap of n+1 nodes)
Move both pointers forward together until fast is null
Now slow is at the node before the target
Remove the target: slow.next = slow.next.next
Return dummy.next as the new head

Why n+1 steps for fast?

We want slow to stop at the node before the target (to perform the deletion). If we moved fast by only n steps, slow would land on the target itself. By using n+1, we ensure slow stops one position earlier.

Trace: Remove 2nd from end of [1,2,3,4,5]
Step	fast position	slow position	Gap	Action
Init	dummy	dummy	0	Both at dummy
Move fast 1	1	dummy	1	Advance fast
Move fast 2	2	dummy	2	Advance fast
Move fast 3	3	dummy	3	Gap = n+1 = 3, start moving both
Move both	4	1	3	Both advance
Move both	5	2	3	Both advance
Move both	null	3	—	fast is null, stop
Remove	—	3	—	slow.next = slow.next.next (skip 4)

One-Pass Implementation

remove_nth_one_pass.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
62
def remove_nth_from_end(head: ListNode, n: int) -> ListNode:
    """
    Remove nth node from end using one pass with two pointers.
    
    Time Complexity: O(L) - single traversal
    Space Complexity: O(1) - only uses three pointers
    
    Key insight: Maintain a gap of n+1 between fast and slow.
    When fast reaches null, slow is at the node BEFORE the target.
    """
    # Dummy node handles edge case of removing the head
    dummy = ListNode(0)
    dummy.next = head
    
    # Both pointers start at dummy
    fast = dummy
    slow = dummy
    
    # Move fast pointer n+1 steps ahead
    # This creates the gap we need
    for _ in range(n + 1):
        fast = fast.next
    
    # Move both pointers until fast reaches the end
    while fast is not None:
        fast = fast.next
        slow = slow.next
    
    # Now slow is at the node BEFORE the target
    # Skip over the target node
    slow.next = slow.next.next
    
    # Return the head (skip dummy)
    return dummy.next
 
 
def remove_nth_from_end_explicit(head: ListNode, n: int) -> ListNode:
    """
    Same algorithm with more explicit variable naming.
    """
    # Create dummy to handle edge case uniformly
    dummy = ListNode(0, head)
    
    # 'ahead' will be n+1 steps ahead of 'behind'
    ahead = dummy
    behind = dummy
    
    # Create the gap: move 'ahead' by n+1 positions
    for i in range(n + 1):
        ahead = ahead.next
    
    # Move both until 'ahead' hits the end
    # At this point, 'behind' is just before the target
    while ahead:
        ahead = ahead.next
        behind = behind.next
    
    # Delete: skip over the target node
    node_to_remove = behind.next
    behind.next = node_to_remove.next
    
    return dummy.next

Why n+1, Not n?

A common mistake is moving fast by exactly n steps. This leaves slow pointing AT the target, not before it. Since we need to modify slow.next.next, we need slow to be one node before the target. Always use n+1 steps for the initial gap.

Edge Cases Deep Dive

The edge cases for this problem reveal why the dummy node is essential:

Edge Case 1: Removing the Head

Input: [1, 2, 3], n = 3
Output: [2, 3]

The 3rd node from the end is the head itself. Without a dummy node, we'd need special-case logic. With a dummy:

Gap of 4 positions (n+1 = 4)
fast moves: dummy → 1 → 2 → 3 → null
slow stays at dummy
slow.next = slow.next.next skips node 1
dummy.next = 2, which is correct

Edge Case 2: Single Node List

Input: [1], n = 1
Output: []

The only node is removed. dummy.next becomes null.

Edge Case 3: Two Nodes, Remove First

Input: [1, 2], n = 2
Output: [2]

Edge Case 4: Two Nodes, Remove Last

Input: [1, 2], n = 1
Output: [1]

test_remove_nth.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
def test_remove_nth_edge_cases():
    """Comprehensive edge case testing."""
    
    def create_list(values):
        if not values:
            return None
        head = ListNode(values[0])
        curr = head
        for val in values[1:]:
            curr.next = ListNode(val)
            curr = curr.next
        return head
    
    def to_array(head):
        result = []
        while head:
            result.append(head.val)
            head = head.next
        return result
    
    # Test 1: Standard case
    result = remove_nth_from_end(create_list([1,2,3,4,5]), 2)
    assert to_array(result) == [1,2,3,5], "Failed: standard case"
    
    # Test 2: Remove head (n = length)
    result = remove_nth_from_end(create_list([1,2,3]), 3)
    assert to_array(result) == [2,3], "Failed: remove head"
    
    # Test 3: Remove tail (n = 1)
    result = remove_nth_from_end(create_list([1,2,3]), 1)
    assert to_array(result) == [1,2], "Failed: remove tail"
    
    # Test 4: Single node
    result = remove_nth_from_end(create_list([1]), 1)
    assert result is None, "Failed: single node"
    
    # Test 5: Two nodes, remove first
    result = remove_nth_from_end(create_list([1,2]), 2)
    assert to_array(result) == [2], "Failed: two nodes, remove first"
    
    # Test 6: Two nodes, remove last
    result = remove_nth_from_end(create_list([1,2]), 1)
    assert to_array(result) == [1], "Failed: two nodes, remove last"
    
    print("All edge case tests passed! ✓")

The Dummy Node Pattern

The dummy node eliminates special-case code for modifying the head. When the problem might require changing the first node, adding a dummy before the head creates a uniform 'previous node' for all positions. This pattern appears in many linked list problems: insertion, deletion, merging, and more.

Visual Proof of Correctness

Let's rigorously prove why the gap technique works.

Setup:

List has L nodes
We want to remove the nth node from the end
This is the (L - n + 1)th node from the beginning (1-indexed)

Key Observation:

We need to stop at node (L - n) to perform the deletion. If slow is at position (L - n), it can set slow.next = slow.next.next to skip the target.

The Gap Invariant:

After moving fast by (n + 1) steps, fast is at position (n + 1) (assuming dummy is position 0).

When we move both pointers together and fast reaches position (L + 1) (null, one past the last node), slow will be at position:

slow_position = fast_position - (n + 1) = (L + 1) - (n + 1) = L - n

This is exactly the node before the target! ✓

Position Analysis for n=2, L=5
Position (0-indexed)	Content	Role
0	dummy	Placeholder
1	node 1	—
2	node 2	—
3	node 3	slow ends here (L-n = 5-2 = 3)
4	node 4	TARGET (2nd from end)
5	node 5	—
6	null	fast ends here (L+1 = 6)

Why This Always Works:

The gap of (n+1) is maintained throughout the traversal. When fast crosses from node L to null (position L+1), slow is guaranteed to be at position (L+1) - (n+1) = L - n. Since node (L - n) is immediately before the target node (L - n + 1), this is exactly where we need to be for deletion.

Boundary Check:

When n = L (remove head): slow stays at dummy, fast moves through entire list
When n = 1 (remove tail): slow ends at second-to-last node
Both extremes work correctly with the same code

Variations and Extensions

The gap technique extends to many related problems:

Variation 1: Return (not remove) the Nth Node from End

Simpler: use gap of n (not n+1), and return slow when fast is null.

Variation 2: Find the Middle of a List

Use slow and fast with fast moving twice as fast. When fast reaches end, slow is at middle.

Variation 3: Find Kth Node from End in One Pass

Same as finding nth, just return instead of delete.

Variation 4: Split List at Nth from End

Find the node before the split point, then sever the connection.

gap_variations.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
def get_nth_from_end(head: ListNode, n: int) -> ListNode:
    """Return (not remove) the nth node from end."""
    fast = slow = head
    
    # Create gap of n
    for _ in range(n):
        fast = fast.next
    
    # Move together until fast reaches end
    while fast:
        fast = fast.next
        slow = slow.next
    
    return slow  # This is the nth node from end
 
 
def find_middle(head: ListNode) -> ListNode:
    """Find the middle node of a linked list."""
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow
 
 
def split_at_nth_from_end(head: ListNode, n: int) -> tuple:
    """
    Split list such that second part has n nodes.
    Returns (first_part_head, second_part_head).
    """
    dummy = ListNode(0, head)
    fast = slow = dummy
    
    # Gap of n+1 so slow lands before split point
    for _ in range(n + 1):
        fast = fast.next
    
    while fast:
        fast = fast.next
        slow = slow.next
    
    # slow is the last node of first part
    second_part = slow.next
    slow.next = None  # Sever the connection
    
    return (dummy.next, second_part)
 
 
def nth_from_end_value(head: ListNode, n: int, default=-1) -> int:
    """Return VALUE of nth node from end, or default if doesn't exist."""
    if not head:
        return default
    
    fast = slow = head
    
    # Move fast n steps, checking bounds
    for _ in range(n):
        if not fast:
            return default  # n is larger than list length
        fast = fast.next
    
    # Move both until fast is null
    while fast:
        fast = fast.next
        slow = slow.next
    
    return slow.val

The Pattern Family

All these variations use the same core insight: maintain a predictable relationship between two pointers. Whether it's a fixed gap, a 2x speed difference, or something more complex, the pattern of using pointer relationships to infer positions is fundamental to efficient linked list algorithms.

Common Mistakes and How to Avoid Them

Classic Mistakes in Remove Nth from End

•Using gap of n instead of n+1 — This puts slow AT the target node, but we need to be BEFORE it to perform deletion. Always use n+1 for deletion problems.
•Forgetting the dummy node — Without it, removing the head requires special-case code. The dummy unifies all cases.
•Off-by-one in the gap loop — Use range(n+1) to move n+1 times. Counting errors here cause wrong node removal.
•Not returning dummy.next — If you modify the head, returning the original head gives wrong results. Always return dummy.next.
•Assuming n is valid — If n > length, fast becomes null during gap creation. Production code should validate or handle gracefully.
•Null pointer access — When fast is null unexpectedly (invalid n), accessing fast.next crashes. Guard against this.

safe_remove_nth.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
def remove_nth_from_end_safe(head: ListNode, n: int) -> ListNode:
    """
    Safe version with input validation.
    Returns original list if n is invalid.
    """
    if not head or n <= 0:
        return head
    
    dummy = ListNode(0, head)
    fast = slow = dummy
    
    # Move fast, but check for null (invalid n)
    for _ in range(n + 1):
        if fast is None:
            # n is larger than list length, can't remove
            return head  # Return unchanged
        fast = fast.next
    
    # Standard traversal
    while fast:
        fast = fast.next
        slow = slow.next
    
    # Perform deletion
    slow.next = slow.next.next
    
    return dummy.next

Complexity Analysis

Let's rigorously analyze both approaches:

Two-Pass Approach:

Pass 1: Count nodes — O(L)
Pass 2: Traverse to target — O(L - n) in worst case
Total: O(L) + O(L) = O(L)
Space: O(1) — just a counter and pointer

One-Pass Approach:

Gap creation: O(n+1) = O(n) steps
Simultaneous traversal: O(L - n) steps
Total: O(n) + O(L - n) = O(L)
Space: O(1) — just three pointers and dummy

Are they the same?

Asymptotically, yes—both are O(L). In practice:

Two-pass performs exactly 2L - n node accesses
One-pass performs exactly L + 1 node accesses
One-pass is ~2x fewer operations for average n

Comparison for L=1000, n=100
Approach	Node Accesses	Cache Implications
Two-Pass	2000 - 100 = 1900	Two full traversals, may not cache effectively
One-Pass	1001	Single traversal, better cache locality

When Does It Matter?

For most applications, the difference is negligible. But for very long lists (millions of nodes) or performance-critical paths, the one-pass approach's 2x reduction in memory accesses can be significant. More importantly, it demonstrates the elegant use of invariants in algorithm design.

Summary: Mastering the Gap Technique

The nth-from-end problem showcases one of the most elegant patterns in linked list manipulation. Let's consolidate the key insights:

Key Takeaways

•The gap technique uses two pointers at a fixed distance to locate positions relative to the end without knowing the length.
•For deletion, use a gap of n+1 so the slow pointer stops BEFORE the target, enabling the skip operation.
•The dummy node eliminates edge cases when the head might be removed, unifying all cases into one code path.
•The one-pass approach halves node accesses compared to counting first, though both are O(L).
•The pattern generalizes to finding middle, splitting at position, or any problem requiring position-from-end knowledge.
•Always validate n in production code—invalid input should fail gracefully, not crash.

Mental Model:

Think of the two pointers as beads on a string with a rigid rod between them. As you slide them along, the rod maintains the gap. When the front bead falls off the end, the back bead is exactly where you need it.

What's Next:

In the next page, we'll explore Partitioning Around a Value—rearranging a list so all nodes less than x come before nodes greater than or equal to x, a pattern that connects to quicksort and Dutch National Flag problems.

Page Complete

You've mastered the gap technique for nth-from-end problems. You understand both two-pass and one-pass approaches, the critical role of the dummy node, and how this pattern extends to related problems. The gap technique is now part of your algorithmic toolkit.