DSA Removing the Nth Node from the End

The problem

The problem gives the head of a linked list and a number n. The answer is the same list with one node removed. The removed node is the nth node from the end.

Counting starts at the last node. The last node is the 1st from the end. Its neighbour is the 2nd from the end.

The value of n is always valid here. It sits between 1 and the length of the list. The list holds at least one node.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


cases = [
    ([1, 2, 3, 4, 5], 2, [1, 2, 3, 5]),
    ([1, 2, 3, 4, 5], 5, [2, 3, 4, 5]),
    ([1, 2, 3, 4, 5], 1, [1, 2, 3, 4]),
    ([1], 1, []),
]
for values, n, expected in cases:
    print("list", values, "remove", n, "from end ->", expected)

Read the second row closely. Removing the 5th from the end of a five-node list removes the head. That case breaks naive code most often.

The last row removes the only node. Its answer is the empty list.

Intuition

The first idea converts the problem. The nth node from the end is a fixed position from the start. That position follows from the length.

A five-node list makes it concrete. The 2nd from the end sits at index 3 from the start. The formula is length - n, using zero-based indexes.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


values = [1, 2, 3, 4, 5]
for n in [1, 2, 5]:
    index = len(values) - n
    print("n:", n, "index from start:", index, "value:", values[index])

The conversion is exact. It also needs the length first. Learning the length costs a full walk before any removal work starts.

Removing the head needs special care in that plan. No node stands before the head. Code that unlinks through a previous node has nothing to hold there.

Brute force

The brute force counts the length in a first walk. It then walks to the node before the target. One link change skips the target.

The head case gets its own branch. Removing the head returns the second node as the new head. Every other target unlinks through its previous node.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


def remove_brute(head, n):
    length = 0
    node = head
    while node is not None:
        length += 1
        node = node.next
    steps = length
    target_index = length - n
    if target_index == 0:
        return head.next, steps
    node = head
    for _ in range(target_index - 1):
        node = node.next
        steps += 1
    node.next = node.next.next
    return head, steps

cases = [
    ([1, 2, 3, 4, 5], 2),
    ([1, 2, 3, 4, 5], 5),
    ([1, 2, 3, 4, 5], 1),
    ([1], 1),
]
for values, n in cases:
    new_head, steps = remove_brute(build(values), n)
    print(values, "n:", n, "->", values_of(new_head), "node visits:", steps)

Every case from the start of the article passes. The head case passes only through its special branch. That branch is a smell.

The visit count shows the other cost. Five nodes cost five counting visits before the walk even starts. The chain is walked twice in the worst case.

The optimal solution: two pointers with a fixed gap

Hold two pointers n links apart, so when the front pointer reaches the last node the rear pointer sits just before the target. That fixed gap is the key idea.

A dummy head stands before the real head. Both pointers start on the dummy. The fast pointer first moves n steps alone, which opens the gap.

Both pointers then move together, one step each. The gap never changes during that joint walk. The slow pointer ends exactly where the unlink must happen.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


def remove_nth(head, n):
    dummy = Node(0)
    dummy.next = head
    fast = dummy
    slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next is not None:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

cases = [
    ([1, 2, 3, 4, 5], 2),
    ([1, 2, 3, 4, 5], 5),
    ([1, 2, 3, 4, 5], 1),
    ([1], 1),
]
for values, n in cases:
    print(values, "n:", n, "->", values_of(remove_nth(build(values), n)))

All four cases pass through one code path. The dummy head absorbs the head-removal case. Removing the head unlinks through the dummy, like any other node.

No length is counted. The chain is walked once. The answer returns as dummy.next, which is the new head.

Walkthrough

Watch the removal of the 2nd node from the end of [1, 2, 3, 4, 5]. The target is 4. The printout shows both pointers after each stage.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


head = build([1, 2, 3, 4, 5])
dummy = Node(0)
dummy.next = head
fast = dummy
slow = dummy
n = 2
for _ in range(n):
    fast = fast.next
print("gap open: slow at dummy, fast at", fast.value)
while fast.next is not None:
    fast = fast.next
    slow = slow.next
    print("move: slow at", slow.value, "fast at", fast.value)
print("slow sits before target:", slow.next.value)
slow.next = slow.next.next
print("after removal:", values_of(dummy.next))

The gap opens with the fast pointer on 2. The slow pointer still sits on the dummy. Two links separate them, counting the steps the fast pointer took.

Three joint moves end with fast on 5, the last node. Slow sits on 3. Its next node is 4, the target, and one link change removes it.

Complexity

The time cost is O(n) for a list of n nodes, where this n means the length. The fast pointer crosses the chain once, and the slow pointer follows inside the same walk.

The space cost is O(1). Two pointers and one dummy node are stored, whatever the length.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


def fast_moves(head, n):
    dummy = Node(0)
    dummy.next = head
    fast = dummy
    slow = dummy
    moves = 0
    for _ in range(n):
        fast = fast.next
        moves += 1
    while fast.next is not None:
        fast = fast.next
        slow = slow.next
        moves += 1
    return moves

for size in [5, 10, 20, 40]:
    head = build(list(range(1, size + 1)))
    print("nodes", size, "fast moves:", fast_moves(head, 2))

The fast pointer moves exactly the length of the list. Doubling the list doubles the moves. One pass means exactly that, counted.

The brute force adds a counting pass on top. Its growth rate matches, but its constant work is close to double on long lists.

Edge cases and pitfalls

Removing the head is the sharpest case. The gap walk handles it without a branch. The slow pointer simply never leaves the dummy.

Removing the tail is the opposite end. The slow pointer stops on the second-to-last node. Its link is set to None through the skipped tail.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def values_of(head):
    values = []
    node = head
    while node is not None:
        values.append(node.value)
        node = node.next
    return values


def remove_nth(head, n):
    dummy = Node(0)
    dummy.next = head
    fast = dummy
    slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next is not None:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

print("remove head:", values_of(remove_nth(build([1, 2, 3]), 3)))
print("remove tail:", values_of(remove_nth(build([1, 2, 3]), 1)))
print("remove only node:", values_of(remove_nth(build([9]), 1)))
print("remove middle:", values_of(remove_nth(build([1, 2, 3, 4]), 2)))

An off-by-one gap is the classic pitfall. Opening the gap one step too wide lands slow on the target itself. The unlink then removes the node after the target.

Starting the pointers at the head instead of a dummy reopens the head problem. The head case then needs its own branch again. The dummy exists to delete that branch.