TL;DR
Two pointers kept exactly n apart find the predecessor of the target node in one pass. O(sz) time, O(1) space.
Approach 1 — Brute force: array of nodes
Store every node in a Python list; the target’s predecessor is then a direct index away.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
nodes: List[ListNode] = []
node = head
while node:
nodes.append(node)
node = node.next
idx = len(nodes) - n # index of the target node
if idx == 0:
return head.next # target is the head
nodes[idx - 1].next = nodes[idx].next
return head
Time O(sz), space O(sz). With sz <= 30 it runs fine, but the node array is unnecessary bookkeeping that a second pointer avoids, and it fails the one-pass follow-up.
Approach 2 — Two passes: count, then walk
“n from the end” is “(L − n + 1) from the start”. Pass one measures the length L; pass two walks to the predecessor of node L − n. A dummy node in front of the head means the predecessor always exists, even when the head is deleted.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
length = 0
node = head
while node:
length += 1
node = node.next
dummy = ListNode(0, head)
prev = dummy
for _ in range(length - n): # steps to the target's predecessor
prev = prev.next
prev.next = prev.next.next
return dummy.next
Walkthrough on [1, 2, 3, 4, 5], n = 2: length = 5; walk 5 − 2 = 3 steps from the dummy → prev is node 3; splice out node 4 → [1, 2, 3, 5].
Time O(sz) (two passes), space O(1).
Approach 3 — One pass: gap of n between two pointers (optimal)
The length is not needed. What is needed is a pointer that reaches the target’s predecessor exactly when another pointer reaches the end. Give fast a head start of n nodes from the head while slow waits at the dummy, then advance both together until fast steps off the list. The gap of n is preserved, so slow lands n+1 nodes from the end: the predecessor.
The pointers stay n apart. After fast gets its n-step head start on [1, 2, 3, 4, 5] with n = 2:
flowchart LR
D[dummy] --> N1[1] --> N2[2] --> N3[3] --> N4[4] --> N5[5] --> NULL[None]
slow([slow]) -.-> D
fast([fast]) -.-> N3
Both then advance one node at a time until fast reaches None, at which point slow is at node 3, the predecessor of the target.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
slow, fast = dummy, head
for _ in range(n): # open a gap of n
fast = fast.next
while fast: # slide the gap to the end
slow = slow.next
fast = fast.next
slow.next = slow.next.next # slow is the predecessor
return dummy.next
Walkthrough on [1, 2, 3, 4, 5], n = 2:
| step | slow | fast |
|---|
| gap opened | dummy | 3 |
| slide 1 | 1 | 4 |
| slide 2 | 2 | 5 |
| slide 3 | 3 | None |
slow = 3, so slow.next = 5, giving [1, 2, 3, 5]. On [1], n = 1: fast starts past the end (None), the slide loop never runs, slow = dummy, and dummy.next = None — the empty list, no special case needed.
Time O(sz) in a single pass, space O(1).
Common pitfalls
- Deleting the head: any version without a dummy node needs an explicit
if branch. The dummy handles [1], n = 1 and [1,2], n = 2 without special casing.
- Off-by-one in the gap: starting
slow at the dummy but fast at the head builds in the extra +1, so slow stops at the predecessor, not the target. Start both at the same node and you stop one node late.
- Stopping the slide at
fast.next vs fast: be consistent with where fast started, and trace a 2-node example before trusting it.
- Returning
head instead of dummy.next: wrong whenever the head was the deleted node.
Pattern takeaway
A fixed offset from the end of a singly linked list is found in one pass by two pointers separated by that offset: when the leader reaches the end, the trailer is at the target. Combine with a dummy predecessor for any deletion, and the head is no longer a special case.