Remove Nth Node From End of List — Editorial

Opening the reading…

Intuitionturning a position from the end into a position from the front

A singly linked list only lets you move forward, so it cannot jump to the n-th node from the end directly. The useful observation is that two pointers can preserve a distance of n nodes. When the front pointer reaches the end, the back pointer is exactly n nodes behind it, at the node that must be removed.

The link you need to change belongs to the node before the target, not to the target itself. Start both pointers at a dummy node placed before the real head, move the front pointer n + 1 steps, and then move both together until the front pointer is null. The back pointer then stops before the target, even when the target is the original head.

The fixed gap converts a distance from the end into a predecessor from the front.

Approachone traversal, with the head case handled normally

Create a dummy node whose next pointer is head, because removing the original head otherwise needs a separate update to the returned pointer.

Set front and back to dummy, because both pointers need the same starting reference before the gap is created.

Advance front exactly n + 1 times, because back must finish on the predecessor of the target rather than on the target itself.

Move front and back together while front is not null, because each paired move preserves the gap and stops back at the same relative position from the end.

Save back->next as the node to remove, because that is the target identified by the maintained gap.

Set back->next to the target's next pointer, because bypassing one link removes the target from the chain without changing any other node.

Delete the removed node, save dummy->next, delete the dummy, and return the saved head, because the dummy is temporary while the returned list must begin at the possibly changed real head.

Complexitythe list is traversed once and no collection grows

MEASURE	BOUND	WHY
Time	O(sz)	The front pointer advances n + 1 times and then both pointers advance together until front reaches null. Each pointer moves only forward, so the total number of link traversals is linear in the sz nodes.
Space	O(1) extra	Only three pointer variables and one temporary node pointer are used; the returned list is required output and is excluded. The bound does not degrade for any list shape because a linked list has no recursive call stack or auxiliary structure proportional to its length.

Here sz is the number of nodes in the input list.

Annotated solutionC++ · one-pass two-pointer solution with a dummy predecessor

CPPThe front pointer creates a gap of n + 1 links, leaving back directly before the node to unlink.

#include <cstddef>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* front = dummy;
        ListNode* back = dummy;

        for (int i = 0; i <= n; ++i) {
            front = front->next;
        }

        while (front != nullptr) {
            front = front->next;
            back = back->next;
        }

        ListNode* toDelete = back->next;
        back->next = toDelete->next;

        ListNode* newHead = dummy->next;
        delete toDelete;
        delete dummy;
        return newHead;
    }
};

The loop uses i <= n rather than i < n because front starts on the dummy and must end n + 1 links ahead. That extra link places back before the target. The dummy is what makes n equal to the list length safe: front can move through the original head and finish at null without any special head-removal branch.

The two-pass alternativea simpler position calculation at the cost of another traversal

A competent alternative first counts the nodes, then converts the request into an index from the front. If the list has sz nodes, the target is at zero-based position sz - n. To unlink it, walk to position sz - n - 1 from the dummy. This is not an asymptotic optimisation: it still uses O(sz) time and O(1) extra space, but some readers find the explicit count easier to debug.

CPPTwo-pass version: count the list, then walk directly to the predecessor of position size - n.

#include <cstddef>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        int size = 0;
        for (ListNode* node = head; node != nullptr; node = node->next) {
            ++size;
        }

        ListNode* previous = dummy;
        for (int i = 0; i < size - n; ++i) {
            previous = previous->next;
        }

        ListNode* toDelete = previous->next;
        previous->next = toDelete->next;

        ListNode* newHead = dummy->next;
        delete toDelete;
        delete dummy;
        return newHead;
    }
};