Remove Nth Node From End of List | Leetcode 19

Welcome to our comprehensive breakdown of Remove Nth Node From End of List (Leetcode 19). Linked List problems natively lack array properties like .length() or direct indexing, meaning we have to be extremely clever about how we track horizontal depth.

Problem Statement

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1: head = [1, 2, 3, 4, 5], n = 2 => Output: [1, 2, 3, 5] (The end of the list is 5. The 2nd node from the end is 4. We remove 4 and return the new list).

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

Approach 1: Two-Pass Strategy (Calculate Length)

If we want to remove the Nth node from the end, that is mathematically identical to removing the (Length - N)th node from the start!

Since a Linked List doesn't inherently tell us its length, our first pass will simply be traversing all the way to a null pointer to manually count up Length. Our second pass will walk specifically Length - N - 1 steps deep to grab the node physically preceding our target node, allowing us to natively bridge over it natively.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # Dummy node protects against edge cases where we delete the original head
        dummy = ListNode(0, head)
        
        # Pass 1: Measure Length
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next
            
        # Pass 2: Navigate exactly to the node sequentially prior to the target
        curr = dummy
        for _ in range(length - n):
            curr = curr.next
            
        # Bridge over the target node safely
        curr.next = curr.next.next
        
        return dummy.next

Complexity Analysis

Approach 2: One-Pass Delay Pointers (Optimal)

In an interview, they are guaranteed to ask if you can do this iteratively in a single pass.

We can use two pointers: a fast and a slow. If we separate fast and slow by exactly n steps of distance... then by the time the fast pointer violently hits the end of the linked list (null), our slow pointer will be hovering precisely n steps behind it!

graph LR
    A["Dummy"] --> B["1"]
    B --> C["2"]
    C --> D["3"]
    D --> E["4"]
    E --> F["5"]
    
    A -.->|"slow"| A
    C -.->|"fast is n=2 steps ahead"| C
    
    subgraph Iteration Completes...
    D -.->|"slow naturally lands before target!"| D
    F -.->|"fast hits End!"| Null
    end
    
    style D fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow = dummy
        fast = dummy
        
        # Propel the fast pointer strictly 'n' nodes ahead
        for _ in range(n):
            fast = fast.next
            
        # Shift them forward in tandem
        while fast and fast.next:
            slow = slow.next
            fast = fast.next
            
        # Slow pointer is hovering immediately behind target node. Safely Bypass.
        slow.next = slow.next.next
        
        return dummy.next

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (19)