Removing the Nth Node from the End

Use two pointers separated by exactly n nodes. Advance the fast pointer n steps, then move both pointers together until the fast one reaches the end. At that point the slow pointer sits on the node before the one you want to remove.

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


def build(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head


def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out


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


print(to_list(remove_nth(build([1, 2, 3, 4, 5]), 2)))
print(to_list(remove_nth(build([1, 2, 3, 4, 5]), 5)))

The outputs are 1, 2, 3, 5 and 2, 3, 4, 5. Removing the second from the end drops the 4, and removing the fifth from the end of a five element list drops the first element.

The mechanism is that the gap between the pointers is what identifies the target. When the fast pointer has walked off the end, exactly n nodes separate it from the slow pointer, and the node the slow pointer points at is the one n positions from the end, which is the node before the one to remove. Unlinking it is then a single assignment to the previous node's next pointer.

The trade-off to name is that this needs the length, which a two pointer approach gets for free. The obvious alternative counts the nodes in a first pass, computes the index from the end, and walks again, which is two passes but easier to follow. The dummy node is what makes the single pass version uniform: without it, removing the head would need a separate branch, because there is no previous node to relink. The version above also assumes n is valid, so a guard for an out of range n belongs in production code.

Walk to the node before the last one and set its next pointer to nothing. The trick is that you need a reference to the second to last node, so you keep moving while the current node still has a next node that itself has a next node.

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


def build(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head


def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out


def remove_last(head):
    if head is None or head.next is None:
        return None
    current = head
    while current.next.next:
        current = current.next
    current.next = None
    return head


print(to_list(remove_last(build([1, 2, 3]))))
print(to_list(remove_last(build([1]))))

The outputs are 1, 2 and an empty list. Removing the last node of a three element list leaves the first two, and a one element list becomes empty.

The mechanism is the loop condition. It keeps advancing while the node after the current one exists, which means the current node is always at least two positions from the end. When the loop stops, the current node is the second to last and can simply be unlinked.

The trade-off to name is that this needs two special cases at the start, because removing the last node of a one element list leaves nothing, and a list of one node has no previous node to unlink. The dummy head pattern removes both cases by giving you a node that always exists before the list, and then the only thing you need to handle is returning the dummy's next pointer rather than the argument. The generalisation of that pattern is the two pointer solution in the previous answer, which removes the nth node from the end for any n in one pass.