Deleting the Nth Node from the End of a Linked List in One Pass

I. Problem Overview

Problem Requirement: Given the head node head of a singly linked list, delete the nth node from the end of the list and return the head node of the modified list.

Challenges:

A singly linked list cannot be traversed in reverse, so you cannot directly find a node by counting backward from the end;
The conventional solution requires a first pass to count the list length and a second pass to delete the node, which is less efficient;
A special edge case exists: when the first node of the list needs to be deleted, operating directly on the head node can cause null pointer errors and node loss.

Optimal Solution Approach: Dummy head node + fast and slow pointers (two-pointer) single-pass method, which completes the deletion in only one traversal of the list, achieving optimal time complexity.

II. Core Algorithm Principles

1. The Role of the Dummy Head Node

This is the key to solving the edge cases in this problem. We manually add a virtual node with a value of 0 to the very front of the list, and point its successor to the original head node.

Core Value: Unifies the deletion logic for all nodes. Regardless of whether the head, a middle, or the tail node is deleted, the node to be deleted will always have a predecessor node. This completely avoids the special case of having no preceding node when deleting the head, eliminating the need for separate boundary-checking code.

2. Core Logic of Fast and Slow Pointers

By using a step difference between two pointers, we can precisely locate the predecessor of the nth node from the end:

Both the fast and slow pointers initially point to the dummy head node;
The fast pointer moves forward n steps alone, creating a fixed gap of n nodes between the fast and slow pointers;
The fast and slow pointers then move forward together synchronously until the fast pointer reaches the last node of the list;
At this moment, the slow pointer is precisely positioned at the node before the nth node from the end;
Modify the slow pointer's next reference to skip the target node, completing the deletion.

III. Complete Code with Line-by-Line Explanation

/**
 * Definition for singly-linked list.
 * Linked list node constructor: default value 0, default next is null
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head The head node of the original list
 * @param {number} n The position from the end of the node to delete
 * @return {ListNode} The head node of the list after deletion
 */
var removeNthFromEnd = function(head, n) {
    // 1. Create a dummy head node and attach it to the front of the original list
    const dummy = new ListNode(0, head);
    // 2. Initialize fast and slow pointers, both pointing to the dummy head node
    let slow = dummy, fast = dummy;

    // 3. Fast pointer moves n steps ahead to build an n-node gap
    while(n--){
        fast = fast.next;
    }

    // 4. Fast and slow pointers move together until fast reaches the end of the list
    while(fast.next && slow.next){
        fast = fast.next;
        slow = slow.next;
    }

    // 5. Delete the node after slow (the nth node from the end)
    slow.next = slow.next.next;

    // 6. Return the real head node of the new list (skipping the dummy node)
    return dummy.next;
};

Detailed Line-by-Line Analysis

1. Create the dummy head node

const dummy = new ListNode(0, head);

Generates an empty node with a value of 0, whose next pointer points directly to the original head node. The list structure now becomes: dummy -> all original list nodes.

2. Initialize the two pointers

let slow = dummy, fast = dummy;

The initial positions of the fast and slow pointers are unified, both pointing to the dummy head node. This ensures a consistent starting state, laying the groundwork for creating a gap later.

3. Fast pointer moves n steps ahead

while(n--){fast = fast.next;}

n-- evaluates first and then decrements, so the loop executes exactly n times, moving the fast pointer forward by n positions. After execution, the gap between the fast and slow pointers is strictly n nodes, which is the core of the precise positioning.

4. Two pointers traverse synchronously to the end of the list

while(fast.next&&slow.next){fast = fast.next;slow = slow.next;}

The loop condition fast.next means: continue moving as long as the fast pointer is not the last node.

When the loop finishes, the fast pointer stops at the last valid node of the list, and the slow pointer stops exactly at the predecessor of the nth node from the end.

Side note: slow.next is a redundant safety check to prevent extreme null pointer errors and does not affect the normal logic.

5. Execute the node deletion

slow.next = slow.next.next;

Directly sets the slow pointer's next to point to the 'successor of the node to be deleted', breaking the link to the target node. The node is automatically garbage collected, completing the deletion.

6. Return the new head node of the list

return dummy.next;

You cannot return the original head! If the original head node was deleted, the original head is invalid. dummy.next always points to the real head node of the list after deletion, adapting to all scenarios.

IV. Complete Walkthrough with an Example

Test Case: List [1,2,3,4,5], delete the 2nd node from the end (which is node 4)

Build the dummy node: dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5
Initial pointers: slow = dummy, fast = dummy
Fast pointer moves 2 steps ahead: fast moves to 1, then 2. The gap between fast and slow is now 2.
Synchronous traversal:
1. fast=2, slow=0 -> fast=3, slow=1
2. fast=3, slow=1 -> fast=4, slow=2
3. fast=4, slow=2 -> fast=5, slow=3
Now fast.next = null, the loop terminates, and slow stops at node 3 (the predecessor of the target node 4)
Execute deletion: 3.next = 4.next, the list becomes 0->1->2->3->5
Return dummy.next, final result: [1,2,3,5]

V. Comprehensive Testing of Core Edge Cases

Edge Case 1: Single-node list (deleting the only node)

Input: head=[1], n=1

Process: dummy->1 -> fast moves 1 step to 1 -> fast.next is null, loop does not execute -> slow=dummy -> dummy.next=null, returns an empty list. Result is correct.

Edge Case 2: Deleting the head node

Input: head=[1,2], n=2 (the 2nd from the end is the head node 1)

Process: dummy->1->2 -> fast moves 2 steps to 2 -> loop terminates -> slow=dummy -> deletes 1, result is [2].

Edge Case 3: Deleting the tail node

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

Process: fast moves 1 step to 1 -> synchronous traversal until fast=3, slow=2 -> deletes tail node 3, result is [1,2].

VI. Algorithm Complexity Analysis

Time Complexity O(L) : L is the total number of nodes in the list. The entire code only traverses the list once, with no repeated traversals, making it highly efficient.
Space Complexity O(1) : Only 1 dummy node and 2 pointer variables are created, using a constant amount of extra space. No additional containers or recursion stack overhead.

VII. Summary of Common Mistakes

Not using a dummy node: This leads to having no predecessor node when deleting the head, requiring extensive boundary checks in the code, which is redundant and error-prone.
Incorrect loop condition: If you write while(fast), the fast pointer will go to null, causing the slow pointer to stop at the target node itself, making deletion impossible.
Returning the original head: When the head node is deleted, the original head is invalid. You must return dummy.next.
Incorrect n-step traversal logic: The fast pointer must move ahead first, and then both must move synchronously. Reversing the order will lead to a positioning error.

VIII. Solution Summary

The core essence of this problem is unifying edge cases with a dummy node + positioning via a fast-slow pointer gap. It solves the problem of finding a node from the end in a single pass, avoids the two-pass flaw of conventional solutions, and perfectly handles all extreme boundary scenarios. It is a classic template for the two-pointer technique on linked lists and can be directly reused to solve similar linked list positioning and deletion problems.