Remove Nth Node From End of List (LeetCode 19)

The problem

You get the head of a singly linked list and an integer n. Remove the n-th node counting from the end (n = 1 is the last node) and return the head of the resulting list. n is always between 1 and the list length.

Input:  1 -> 2 -> 3 -> 4 -> 5,  n = 2
Output: 1 -> 2 -> 3 -> 5

Counting from the end, 5 is first and 4 is second, so 4 goes.

How to think about it

Start with brute force. Walk the list once to get its length L. The node to remove is at position L − n from the start (0-indexed), so walk again to the node just before it and unlink. That is O(n) time and O(1) space, in two passes. It is a fine answer; the follow-up asks for one pass.

What you really need. To unlink a node in a singly linked list, you must stand on the node before it. So the question is: how do you stop one node before “n from the end” without knowing the length?

The key insight: a fixed gap between two pointers. Move a f pointer n nodes ahead first. Now start s and move both one step at a time. The gap stays exactly n, so when f is on the last node, s is n nodes behind it, which is exactly the node before the target. A dummy node in front of the head means “before the target” always exists, even when the target is the head itself.

Which pattern is this? Two pointers at the same speed with a head start (a cousin of fast & slow). The tell is “k-th from the end, in one pass”.

Approach

1. Create a dummy node d whose next is head. Put f and s on d.
2. Move f forward n times.
3. While f.next exists, move f and s one step each. f ends on the last node.
4. s is now just before the target. Skip it: s.next = s.next.next.
5. Return d.next, which is the new head.

Solution

# ListNode is LeetCode's class: ListNode(val=0, next=None)
def remove_nth_from_end(head, n):
    d = ListNode(0, head); f = s = d          # dummy handles removing the head
    for _ in range(n): f = f.next             # open a gap of n nodes
    while f.next: f = f.next; s = s.next      # stop when f is on the last node
    s.next = s.next.next                      # s is just before the target
    return d.next
# remove_nth_from_end([1,2,3,4,5], 2) -> [1,2,3,5]

Dry run

On 1 -> 2 -> 3 -> 4 -> 5 with n = 2 (D is the dummy):

s is on node 3, so s.next (node 4) is skipped and the result is 1 -> 2 -> 3 -> 5.

Complexity

• Time: O(L) for a list of length L. f walks the list once; s walks less.
• Space: O(1). One dummy node and two pointers.

Edge cases and pitfalls

• Removing the head (n equals the length): without the dummy you would need a special case. With it, s stays on the dummy and d.next becomes the second node. On 1 -> 2 with n = 2 the result is 2.
• Single node, n = 1: the result is an empty list (None).
• Off by one. The loop runs while f.next, not while f. With while f, s would land on the target itself, and you can’t unlink a node from itself in a singly linked list.
• Returning head instead of d.next breaks when the head was the node removed.

Related problems

• Middle of the Linked List (LeetCode 876): two pointers at different speeds instead of a fixed gap.
• Rotate List (LeetCode 61): find the k-th node from the end and re-link there.
• Remove Duplicates from Sorted List II (LeetCode 82): the same dummy-node trick for deleting from the front.