Remove Nth Node From End of List

LeetCode 19: Remove Nth Node From End of List Solution & Explanation

Problem Overview

TL;DR: Use two pointers with a fixed separation of $n$ nodes to locate the node preceding the target in a single pass, enabling efficient removal.

The LeetCode 19: Remove Nth Node From End of List problem asks us to delete the $n$-th node from the end of a singly linked list and return the head of the modified list. The challenge lies in identifying the target node's position relative to the end of the list, rather than the beginning, particularly when the total length of the list is unknown. The optimal solution for interviews requires achieving this in a single pass.

Brute Force Approach for Remove Nth Node From End of List

The naive approach to solving this problem involves a two-pass strategy. Since we do not know the length of the linked list initially, we cannot immediately determine which node is the $n$-th from the end.

1. First Pass: Traverse the entire linked list starting from the head to count the total number of nodes, denoted as $L$.
2. Calculate Target: The node to remove is located at the index $L - n$ (0-indexed). The node before the target (the predecessor) is at index $L - n - 1$.
3. Second Pass: Traverse the list again from the head, stopping at the $(L - n - 1)$-th node.
4. Removal: Update the next pointer of the predecessor to skip the target node.

Pseudo-code:

function removeNthFromEnd(head, n):
    length = 0
    current = head
    while current is not null:
        length++
        current = current.next
        
    targetIndex = length - n
    if targetIndex == 0: return head.next
    
    current = head
    for i from 0 to targetIndex - 1:
        current = current.next
        
    current.next = current.next.next
    return head

Why it is suboptimal: While the time complexity is $O(L)$ and space is $O(1)$, this approach requires traversing the list twice (specifically $2L - n$ steps). The problem statement includes a follow-up asking for a one-pass solution. In high-performance scenarios or interviews, reducing the number of traversals demonstrates a deeper understanding of pointer manipulation.

Algorithm Strategy: Two Pointer Patterns

1. Dummy Node Initialization: Create a dummy node (sentinel) pointing to the head of the list. This simplifies edge cases, such as removing the head node itself (where the $n$-th node from the end is the first node).
2. Pointer Setup: Initialize two pointers, slow and fast, both pointing to the dummy node.
3. Create the Gap: Advance the fast pointer forward by $n + 1$ steps. This establishes the necessary separation so that slow will point to the predecessor of the target node later.
4. Slide the Window: Move both slow and fast pointers forward one node at a time until fast becomes null.
5. Perform Deletion: At this state, slow points to the node immediately before the target node. Update slow.next to point to slow.next.next, effectively removing the target node from the list.
6. Return Result: Return dummy.next as the new head of the list.

Execution Flow

Let's trace the algorithm with Input: head = [1, 2, 3, 4, 5], n = 2.

1. Setup:

   • Create dummy node with val=0, next=head.
   • List: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null.
   • slow points to dummy.
   • fast points to dummy.

2. Create Gap:

   • Move fast $n + 1$ (which is 3) steps.
   • Step 1: fast at 1.
   • Step 2: fast at 2.
   • Step 3: fast at 3.
   • Current state: slow at dummy, fast at 3. Gap is established.

3. Slide Window:

   • Loop condition: fast is not null.
   • Iteration 1:
     • slow moves to 1.
     • fast moves to 4.
   • Iteration 2:
     • slow moves to 2.
     • fast moves to 5.
   • Iteration 3:
     • slow moves to 3.
     • fast moves to null.
   • Loop terminates because fast is null.

4. Deletion:

   • slow is at node 3. The target to remove is slow.next (node 4).
   • Operation: slow.next = slow.next.next (points 3 to 5).
   • List becomes: dummy -> 1 -> 2 -> 3 -> 5 -> null.

5. Return:

   • Return dummy.next (node 1).

Proof of Correctness

Let $L$ be the length of the list. The nodes are indexed $0$ to $L-1$. The $n$-th node from the end corresponds to the index $L - n$. The predecessor of this node is at index $L - n - 1$.

We start with a dummy node at index $-1$.

1. We advance fast by $n + 1$ steps. fast is now at index $n - 1$ (relative to the original list, or $n$ steps from dummy).
2. The distance from fast to the end (null, effectively index $L$) is $L - (n - 1) = L - n + 1$ steps? No, simpler: fast starts at dummy. After $n+1$ steps, fast is at the $n$-th node of the list.
3. Let $k$ be the number of steps fast takes to reach null from its current position.
4. slow also takes $k$ steps from the dummy node.
5. When fast reaches null, it has traversed a total of $L + 1$ nodes (including dummy).
6. slow is $n + 1$ steps behind fast.
7. Therefore, slow's position is $(L + 1) - (n + 1) = L - n$ steps from the start (including dummy).
8. In terms of list indices (0-indexed), slow lands on index $L - n - 1$, which is exactly the predecessor of the target node at $L - n$.

Pattern Reuse Notes

The Two Pointer pattern used here is fundamental for linked list problems involving position finding.

• LeetCode 876: Middle of the Linked List: Uses two pointers moving at different speeds (1x and 2x) to find the middle. While the "separation" isn't fixed, the concept of using relative pointer positions to find a target without calculating length is identical.
• LeetCode 2095: Delete the Middle Node of a Linked List: Directly applies the logic from LC 876 to find the predecessor of the middle node, similar to how we find the predecessor of the $n$-th node here.

Reference Implementation

C++ Solution for LeetCode 19

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* removeNthFromEnd(ListNode* head, int n) {
14        // Use a dummy node to handle edge cases like removing the head
15        ListNode* dummy = new ListNode(0);
16        dummy->next = head;
17        
18        ListNode* slow = dummy;
19        ListNode* fast = dummy;
20        
21        // Advance fast pointer so that the gap between fast and slow is n nodes
22        // We move n + 1 times to land slow on the predecessor of the target
23        for (int i = 0; i <= n; ++i) {
24            fast = fast->next;
25        }
26        
27        // Move both pointers until fast reaches the end
28        while (fast != nullptr) {
29            slow = slow->next;
30            fast = fast->next;
31        }
32        
33        // Remove the nth node from the end
34        ListNode* nodeToDelete = slow->next;
35        slow->next = slow->next->next;
36        delete nodeToDelete; // Good practice in C++ to free memory
37        
38        ListNode* newHead = dummy->next;
39        delete dummy; // Clean up dummy node
40        return newHead;
41    }
42};

Java Solution for LeetCode 19

1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    public ListNode removeNthFromEnd(ListNode head, int n) {
13        // Dummy node simplifies edge cases (e.g., removing the only node)
14        ListNode dummy = new ListNode(0);
15        dummy.next = head;
16        
17        ListNode slow = dummy;
18        ListNode fast = dummy;
19        
20        // Move fast pointer n + 1 steps ahead
21        for (int i = 0; i <= n; i++) {
22            fast = fast.next;
23        }
24        
25        // Move both pointers until fast reaches the end
26        while (fast != null) {
27            slow = slow.next;
28            fast = fast.next;
29        }
30        
31        // Skip the desired node
32        slow.next = slow.next.next;
33        
34        return dummy.next;
35    }
36}

Python Solution for LeetCode 19

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
8        # Initialize dummy node pointing to head
9        dummy = ListNode(0, head)
10        slow = dummy
11        fast = dummy
12        
13        # Move fast pointer n + 1 steps forward
14        # This ensures slow stops at the node BEFORE the one we want to delete
15        for _ in range(n + 1):
16            fast = fast.next
17            
18        # Move both pointers until fast reaches the end
19        while fast:
20            slow = slow.next
21            fast = fast.next
22            
23        # Delete the target node
24        slow.next = slow.next.next
25        
26        return dummy.next