The task is to delete the node that is n positions away from the tail of a singly-linked list and return the new head. The optimal approach performs the operasion in a single travesral, leveraging a two-pointer technique and a sentinel node.

Key Idea

• Use a sentinel (dummy) node to eliminate edge-case handling for the head.
• Advance the lead pointer n steps ahead.
• Move both lead and lag pointers together until lead reaches the last element.
• The node after lag is the one to remove.

Implementation

struct Node {
    int value;
    Node* next;
    Node() : value(0), next(nullptr) {}
    explicit Node(int v) : value(v), next(nullptr) {}
    Node(int v, Node* n) : value(v), next(n) {}
};

class LinkedListEditor {
public:
    Node* dropNthFromEnd(Node* head, int k) {
        Node sentinel(0, head);   // Guarantees every real node has a predecessor
        Node* lead = &sentinel;
        Node* lag  = &sentinel;

        // Advance lead k steps
        for (int i = 0; i < k; ++i) {
            lead = lead->next;
        }

        // Move both until lead hits the final node
        while (lead->next != nullptr) {
            lead = lead->next;
            lag  = lag->next;
        }

        // Remove the node after lag
        Node* victim = lag->next;
        lag->next = victim->next;
        delete victim;

        return sentinel.next;
    }
};

Walk-through

Consider a list 1 → 2 → 3 → 4 → 5 and k = 2.

1. lead moves two steps: points to 2.
2. Both pointers advance until lead is on 5.
3. lag now points to 3, whose next is 4—the node to delete.
4. Adjust lag->next to 5, removing 4.

Why the Sentinel Mattters

Without it, deleting the first node would require special-case code (head = head->next). The sentinel ensures every node, including the original head, has a predecessor, making the removal logic uniform.

Complexity

• Time: O(L) where L is the list length (single scan).
• Space: O(1) (constant auxiliary pointers).