Reasoning Into CodeArunank Divya Sharan · Python edition← Arunank’s portfolio
Module 11 · Linked Lists and Pointer Mutation

107. Remove Nth Node from End

Bridge · Download this solution · All solutions and shared helpers

Problem

Remove the nth node from the end of a nonempty finite singly linked list, with 1<=n<=length. Return the possibly changed head and reuse all remaining nodes. Use one traversal with two pointers and a dummy predecessor.

Examples

Example 1

list_values(remove_nth_from_end(build_list([1,2,3,4,5]), 2))
=> [1, 2, 3, 5]

Node four is second from the end.

Example 2

list_values(remove_nth_from_end(build_list([1]), 1))
=> []

Removing the only node returns None.

Example 3

list_values(remove_nth_from_end(build_list([1,2]), 2))
=> [2]

The dummy supports removing the head.

Reveal the worked solution and reasoning

Why this mechanism works

Place fast n links ahead of slow, starting both at a dummy. Then move them together until fast reaches the tail. Slow is now immediately before the node to remove. The dummy makes removing the head the same link operation as removing any interior node.

State and boundaries

fast stays n links ahead of slow. When fast.next is None, slow.next is the nth node from the end.

Protocol

  1. Attach head after a dummy.
  2. Move fast n steps.
  3. Advance both until fast is the tail.
  4. Bypass slow.next.
  5. Return dummy.next.

Visualization

dummy -> 1 -> 2 -> 3 -> 4 -> 5
n=2: when fast=5, slow=3
bypass 4: 3.next=5

Python implementation

from structures import ListNode, build_list, list_values

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

list_values(remove_nth_from_end(build_list([1,2,3,4,5]), 2))

L4 remove_nth_from_end: dummy = ListNode(next=head)
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None)

L5 remove_nth_from_end: slow = fast = dummy
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N3(val=0,next=N1,random=None); fast=N3(val=0,next=N1,random=None)

L6 remove_nth_from_end: for _ in range(n):
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N3(val=0,next=N1,random=None); fast=N3(val=0,next=N1,random=None); _=0

L7 remove_nth_from_end: fast = fast.next
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N3(val=0,next=N1,random=None); fast=N1(val=1,next=N2,random=None); _=0

L6 remove_nth_from_end: for _ in range(n):
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N3(val=0,next=N1,random=None); fast=N1(val=1,next=N2,random=None); _=1

L7 remove_nth_from_end: fast = fast.next
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N3(val=0,next=N1,random=None); fast=N2(val=2,next=N4,random=None); _=1

L9 remove_nth_from_end: slow = slow.next
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N1(val=1,next=N2,random=None); fast=N2(val=2,next=N4,random=None); _=1

L10 remove_nth_from_end: fast = fast.next
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N1(val=1,next=N2,random=None); fast=N4(val=3,next=N5,random=None); _=1

... 1 intermediate state changes omitted ...

L10 remove_nth_from_end: fast = fast.next
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N2(val=2,next=N4,random=None); fast=N5(val=4,next=N6,random=None); _=1

L9 remove_nth_from_end: slow = slow.next
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N4(val=3,next=N5,random=None); fast=N5(val=4,next=N6,random=None); _=1

L10 remove_nth_from_end: fast = fast.next
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N4(val=3,next=N5,random=None); fast=N6(val=5,next=None,random=None); _=1

L11 remove_nth_from_end: slow.next = slow.next.next
head=N1(val=1,next=N2,random=None); n=2; dummy=N3(val=0,next=N1,random=None); slow=N4(val=3,next=N6,random=None); fast=N6(val=5,next=None,random=None); _=1

Result: [1, 2, 3, 5]. Node four is second from the end.

list_values(remove_nth_from_end(build_list([1]), 1))

L4 remove_nth_from_end: dummy = ListNode(next=head)
head=N1(val=1,next=None,random=None); n=1; dummy=N2(val=0,next=N1,random=None)

L5 remove_nth_from_end: slow = fast = dummy
head=N1(val=1,next=None,random=None); n=1; dummy=N2(val=0,next=N1,random=None); slow=N2(val=0,next=N1,random=None); fast=N2(val=0,next=N1,random=None)

L6 remove_nth_from_end: for _ in range(n):
head=N1(val=1,next=None,random=None); n=1; dummy=N2(val=0,next=N1,random=None); slow=N2(val=0,next=N1,random=None); fast=N2(val=0,next=N1,random=None); _=0

L7 remove_nth_from_end: fast = fast.next
head=N1(val=1,next=None,random=None); n=1; dummy=N2(val=0,next=N1,random=None); slow=N2(val=0,next=N1,random=None); fast=N1(val=1,next=None,random=None); _=0

L11 remove_nth_from_end: slow.next = slow.next.next
head=N1(val=1,next=None,random=None); n=1; dummy=N2(val=0,next=None,random=None); slow=N2(val=0,next=None,random=None); fast=N1(val=1,next=None,random=None); _=0

Result: []. Removing the only node returns None.

Why the solution is correct

The fixed gap is established before tandem movement and preserved by every paired step. At termination exactly n nodes begin at slow.next through the tail, so bypassing slow.next removes the requested node. The dummy preserves a valid predecessor even when that node is the head.

Time and space

O(length) time and O(1) auxiliary space.

Common mistakes

Advancing fast by a different number requires a different stopping condition. Returning head after removing the first node returns a detached node.

Reasoning card

State: fast stays n links ahead of slow. When fast.next is None, slow.next is the nth node from the end.

Invariant: When fast reaches the end, slow precedes the node to remove.

Decision to rehearse: Create an n-node gap, then advance both pointers.

Finish: Return dummy.next

Transfer exercise

Accept invalid n values and choose a clear error contract without partially mutating the list.