Remove nth Node from End of List
Drop the nth-from-last node in one pass using a fast/slow pointer gap of n.
3 min read
two-pointers linked-list
Problem#
Remove the nth node from the end of a singly linked list and return the head.
Examples#
head = [1,2,3,4,5], n = 2→[1,2,3,5]head = [1], n = 1→[]head = [1,2], n = 1→[1]
Constraints#
- List length in
[1, 30],1 <= n <= length.
Hints#
Hint 1
Two passes works (count then delete). Can you do it in one?
Hint 2
Use a dummy node so removing the head is no special case.
Approach#
Two passes — count length, walk again to
length - n. Clear but two traversals. Gap of n — advance
fast by n first, then move slow and fast together until fast reaches the end. slow stops at the predecessor of the target. Solution#
class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0, head); ListNode *slow = &dummy, *fast = &dummy; for (int i = 0; i < n; ++i) fast = fast->next; while (fast->next) { slow = slow->next; fast = fast->next; } ListNode* del = slow->next; slow->next = del->next; delete del; return dummy.next; }};func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{Next: head} slow, fast := dummy, dummy for i := 0; i < n; i++ { fast = fast.Next } for fast.Next != nil { slow = slow.Next fast = fast.Next } slow.Next = slow.Next.Next return dummy.Next}from typing import Optional
class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) slow = fast = dummy for _ in range(n): fast = fast.next while fast.next: slow = slow.next fast = fast.next slow.next = slow.next.next return dummy.nextfunction removeNthFromEnd(head, n) { const dummy = new ListNode(0, head); let slow = dummy, fast = dummy; for (let i = 0; i < n; i++) fast = fast.next; while (fast.next) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return dummy.next;}class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode slow = dummy, fast = dummy; for (int i = 0; i < n; i++) fast = fast.next; while (fast.next != null) { slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return dummy.next; }}function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { const dummy = new ListNode(0, head); let slow: ListNode = dummy; let fast: ListNode = dummy; for (let i = 0; i < n; i++) fast = fast.next as ListNode; while (fast.next) { slow = slow.next as ListNode; fast = fast.next; } slow.next = (slow.next as ListNode).next; return dummy.next;}Editorial#
The dummy node converts “remove the head” into “remove the second node” — the pointer chain stays uniform. Starting both pointers at the dummy and advancing fast by n creates a permanent n-node gap. When fast->next becomes null, slow sits exactly at the predecessor of the node to delete (because the gap is n, and the last node is at position length, so slow is at length - n, the predecessor).
Complexity#
- Time: O(L) — one pass.
- Space: O(1).
Concept revision#
Related#