Remove Nth Node From End of List

Problem Statement

Given the head of a linked list, remove the $n^{th}$ node from the end of the list and return its head.

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

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

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

Approach: Two Pointers with a Dummy Node

To remove a node from a linked list, we need a pointer to the node immediately preceding it. Finding the $n^{th}$ node from the end in a single pass can be done elegantly using two pointers separated by a specific distance.

Using a Dummy Node at the start of the list is a crucial technique here because it handles edge cases effortlessly (such as when the node to be removed is the very first node in the list).

1. Initialize a Dummy Node: Create a dummy node that points its next to the head of the list. This will be the new anchor.
2. Setup Two Pointers: Initialize two pointers, left and right, both starting at the dummy node.
3. Create the Gap: Move the right pointer forward by exactly n + 1 steps. This establishes a gap of n nodes between left and right.
4. Slide the Window: Move both left and right forward one step at a time until right reaches null (the end of the list).
   • Because of the gap we created, when right hits null, the left pointer will be positioned exactly on the node just before the target node we want to remove.
5. Delete the Target Node: Update the next pointer of the left node to skip the target node: left.next = left.next.next.
6. Return the Result: The true head of the modified list is dummy.next.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
function removeNthFromEnd(head, n) {
    // 1. Initialize a dummy node to handle edge cases
    let dummy = new ListNode(0, head);
    let left = dummy;
    let right = dummy;
    
    // 2. Move right pointer n + 1 steps ahead
    for (let i = 0; i <= n; i++) {
        right = right.next;
    }
    
    // 3. Move both pointers until right reaches the end
    while (right !== null) {
        left = left.next;
        right = right.next;
    }
    
    // 4. Delete the nth node from the end
    left.next = left.next.next;
    
    // 5. Return the head of the modified list
    return dummy.next;
}

Complexity Analysis

• Time Complexity: $O(L)$ where $L$ is the length of the linked list. The algorithm makes exactly one traversal of the list, visiting each node at most once.
• Space Complexity: $O(1)$. We only allocate a single dummy node and two pointers (left, right), resulting in constant extra space.