[/dsa/leetcode]

19 - Remove Nth Node From End of List

Friday, 18 September 2026

<medium> [problem]

A gap of n between two pointers turns a distance from the end into a distance from the front, so one pass finds the node to unlink without ever measuring the length.

{linked list}{two pointers}

Problem

Given the head of a linked list, remove the nth node from the end of the list and return the head.

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Input: head = [1], n = 1
Output: []

Input: head = [1,2], n = 1
Output: [1]

Constraints:

  • The number of nodes is sz, with 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Follow-up: can you do it in one pass?

Approach

The problem is stated from the end and a singly linked list only knows about the front, so the obvious version counts the length first and then walks sz - n nodes. Two passes, and correct.

The one-pass version converts the distance without measuring anything. Put fast n nodes ahead of slow and then advance both at the same speed. The gap never changes, so when fast reaches the end, slow is n nodes from the end too — the offset from the front got discovered for free:

[1,2,3,4,5], n = 2

gap opened   slow=1        fast=3
step         slow=2        fast=4
step         slow=3        fast=5   (fast->next is null, stop)

slow->next is 4, the 2nd from the end

Stopping on fast->next == nullptr rather than fast == nullptr is what leaves slow on the node beforethe target, which is the one that has to be rewired. Deleting from a singly linked list always needs the predecessor.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return head;
        ListNode *slow = head, *fast = head;
        while (n--)
            fast = fast->next;
        if (!fast)
            return head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode *slow = &dummy, *fast = &dummy;
    while (n--) fast = fast->next;
    while (fast->next) {
        slow = slow->next;
        fast = fast->next;
    }
    slow->next = slow->next->next;
    return dummy.next;
}
  • time: O(n) - one pass, sz pointer steps total
  • space: O(1) - two pointers
quantinium © 2026