Remove Nth Node From End Of List#

Problem#

Given the head of a singly linked list and an integer n, remove the n-th node counting from the end of the list, then return the head. It is guaranteed that n is valid for the list length.

Example#

List 1 -> 2 -> 3 -> 4 -> 5 with n = 2 removes node 4, giving 1 -> 2 -> 3 -> 5. With n = 1 on a single-node list, the result is empty.

Brute force#

First walk the list to count its length L, then walk again to the node at position L - n and unlink it. That is two passes.

Optimal approach#

Do it in one pass with two pointers and a dummy head that handles the case of removing the actual first node. Advance a fast pointer n steps ahead of a slow pointer that starts at the dummy. Then move both together until fast reaches the end. At that moment slow sits on the node just before the target, so slow.next = slow.next.next unlinks it. Return dummy.next.

Solution#

 1class ListNode:
 2    def __init__(self, val=0, next=None):
 3        self.val = val
 4        self.next = next
 5
 6
 7def remove_nth_from_end(head: ListNode | None, n: int) -> ListNode | None:
 8    dummy = ListNode(0, head)
 9    fast = slow = dummy
10    for _ in range(n):
11        fast = fast.next
12    while fast.next:
13        fast = fast.next
14        slow = slow.next
15    slow.next = slow.next.next
16    return dummy.next
17
18
19def build(values):
20    head = None
21    for value in reversed(values):
22        head = ListNode(value, head)
23    return head
24
25
26def to_list(node):
27    out = []
28    while node:
29        out.append(node.val)
30        node = node.next
31    return out
32
33
34print(to_list(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)))  # [1, 2, 3, 5]
35print(to_list(remove_nth_from_end(build([1]), 1)))              # []

Complexity#

• Time: O(n), a single pass.
• Space: O(1).

This applies the fast and slow pointers gap technique. Continue with the 60-day challenge.