Problem Description

You are given the head of a singly linked list and an integer n. Your task is to remove the n-th node from the end of the list and return the modified list's head.

For example, if you have a linked list 1 -> 2 -> 3 -> 4 -> 5 and n = 2, you need to remove the 2nd node from the end (which is node with value 4), resulting in 1 -> 2 -> 3 -> 5.

The solution uses a two-pointer technique with fast and slow pointers. First, a dummy node is created pointing to the head to handle edge cases where the head itself needs to be removed. Both fast and slow pointers start at the dummy node.

The fast pointer advances n steps ahead first. This creates a gap of n nodes between the fast and slow pointers. Then both pointers move forward together, one step at a time, maintaining this gap. When fast.next becomes None (meaning fast is at the last node), the slow pointer will be positioned right before the node that needs to be removed.

At this point, slow.next is the node to be deleted. The removal is done by updating slow.next = slow.next.next, effectively bypassing the target node in the linked list. Finally, dummy.next is returned as the new head of the modified list.

This approach works in a single pass through the linked list with O(n) time complexity and O(1) space complexity.

Intuition

The key insight is recognizing that finding the n-th node from the end requires us to somehow relate it to a position from the beginning of the list. Since we don't know the total length of the linked list initially, we need a clever way to identify this position without counting all nodes first.

Think about it this way: if we have two runners on a track, and one runner starts n steps ahead of the other, when the first runner reaches the finish line, where would the second runner be? The second runner would be exactly n steps behind the finish line.

We can apply this same concept to our linked list problem. By maintaining two pointers with a gap of n nodes between them, when the leading pointer reaches the end of the list, the trailing pointer will naturally be positioned at the node just before our target node.

Why do we need to stop at the node before our target? Because in a singly linked list, to remove a node, we need access to its predecessor to update the next reference and bypass the node we want to delete.

The dummy node technique emerges from considering the edge case where we need to remove the head itself (when the list has exactly n nodes). Without a dummy node, we'd need special handling for this case. By adding a dummy node before the head, we ensure there's always a predecessor node, making our logic uniform for all cases.

This approach elegantly solves the problem in one pass - we don't need to traverse the list twice (once to count nodes and once to remove), making it an optimal solution.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

The implementation uses the fast and slow pointer technique with a dummy node to handle edge cases elegantly.

Step 1: Create a dummy node

dummy = ListNode(next=head)

We create a dummy node that points to the head of the linked list. This ensures we always have a predecessor node, even when removing the head itself.

Step 2: Initialize two pointers

fast = slow = dummy

Both fast and slow pointers start at the dummy node. These will maintain a fixed gap to help us locate the node to remove.

Step 3: Advance the fast pointer by n steps

for _ in range(n):
    fast = fast.next

We move the fast pointer forward by exactly n nodes. This creates a gap of n nodes between fast and slow. For example, if n = 2, after this step, fast is 2 nodes ahead of slow.

Step 4: Move both pointers until fast reaches the end

while fast.next:
    slow, fast = slow.next, fast.next

Both pointers now advance together, maintaining their gap of n nodes. The loop continues while fast.next exists (meaning fast hasn't reached the last node yet). When this loop ends, fast is at the last node, and slow is positioned right before the node we need to remove.

Step 5: Remove the target node

slow.next = slow.next.next

Since slow is positioned before the node to remove, we bypass the target node by updating slow.next to point to slow.next.next. This effectively removes the n-th node from the end.

Step 6: Return the new head

return dummy.next

We return dummy.next which is the head of the modified linked list. If the original head was removed, dummy.next correctly points to the new head.

This approach achieves O(n) time complexity with a single pass through the list and O(1) space complexity as we only use two extra pointers regardless of the list size.

Example Walkthrough

Let's walk through a concrete example with the linked list 1 -> 2 -> 3 -> 4 -> 5 and n = 2 (removing the 2nd node from the end, which is node 4).

Initial Setup:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
  ↑
fast
slow

We create a dummy node pointing to head (1), and both fast and slow start at dummy.

Step 1: Advance fast pointer by n=2 steps

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
  ↑           ↑
slow        fast

After moving fast forward 2 times: fast moves from dummy to 1, then from 1 to 2.

Step 2: Move both pointers together until fast.next is None

First move:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
         ↑           ↑
       slow        fast

Second move:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
              ↑           ↑
            slow        fast

Third move:

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
                   ↑           ↑
                 slow        fast

Now fast.next is None (fast is at the last node), so we stop.

Step 3: Remove the target node slow is at node 3, and slow.next is node 4 (our target). We execute:

slow.next = slow.next.next

This makes node 3 point directly to node 5, bypassing node 4:

dummy -> 1 -> 2 -> 3 -> 5 -> None
                   ↑     ↑
                 slow   (4 is removed)

Step 4: Return the result Return dummy.next, which gives us the modified list: 1 -> 2 -> 3 -> 5

The node with value 4 has been successfully removed from the list.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the linked list. The algorithm makes two passes through portions of the list: first, the fast pointer advances n nodes ahead, then both pointers traverse together until the fast pointer reaches the end. In the worst case, this requires traversing approximately 2n nodes, which simplifies to O(n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the dummy node and two pointers (fast and slow), regardless of the input size. No additional data structures that scale with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Edge Case When Removing the Head Node

One of the most common mistakes is forgetting to handle the case where we need to remove the first node of the linked list (when the list has exactly n nodes).

Incorrect Implementation:

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    fast = slow = head  # Starting directly from head instead of dummy
  
    for _ in range(n):
        fast = fast.next
  
    # This will fail when fast is None (removing the head)
    while fast.next:  # NoneType has no attribute 'next'
        slow = slow.next
        fast = fast.next
  
    slow.next = slow.next.next
    return head

Why it fails: When the list has exactly n nodes and we need to remove the head, after advancing fast by n steps, fast becomes None. Trying to access fast.next raises an AttributeError.

Solution: Always use a dummy node that points to the head. This ensures there's always a predecessor node, even when removing the head itself.

2. Off-by-One Error in Pointer Positioning

Another common mistake is confusion about where the pointers should end up, leading to removing the wrong node.

Incorrect Implementation:

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(next=head)
    fast = slow = dummy
  
    # Advancing n+1 times instead of n
    for _ in range(n + 1):  # Wrong!
        fast = fast.next
  
    while fast:  # Should be fast.next
        slow = slow.next
        fast = fast.next
  
    slow.next = slow.next.next
    return dummy.next

Why it fails: This creates a gap of n+1 nodes instead of n, causing the wrong node to be removed. Additionally, using while fast: instead of while fast.next: positions slow one node too far.

Solution:

• Advance fast exactly n times (not n+1)
• Use while fast.next: to ensure slow stops right before the target node

3. Not Validating Input Assumptions

While the problem typically guarantees valid input, in production code, not checking if n is valid can cause issues.

Risky Implementation:

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(next=head)
    fast = slow = dummy
  
    # What if n is larger than the list length?
    for _ in range(n):
        fast = fast.next  # Could become None, then crash on next iteration
  
    # Rest of the code...

Better Practice (for production code):

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(next=head)
    fast = slow = dummy
  
    # Validate that n doesn't exceed list length
    for i in range(n):
        if fast.next is None:
            # Handle invalid n (larger than list length)
            return head  # or raise an exception
        fast = fast.next
  
    while fast.next:
        slow = slow.next
        fast = fast.next
  
    slow.next = slow.next.next
    return dummy.next

4. Memory Leak in Languages with Manual Memory Management

In languages like C or C++, forgetting to free the removed node can cause memory leaks.

C++ Example:

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0, head);
    ListNode* fast = dummy;
    ListNode* slow = dummy;
  
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
  
    while (fast->next) {
        slow = slow->next;
        fast = fast->next;
    }
  
    ListNode* toDelete = slow->next;  // Save reference to node being removed
    slow->next = slow->next->next;
    delete toDelete;  // Free the memory
  
    ListNode* newHead = dummy->next;
    delete dummy;  // Also free the dummy node
    return newHead;
}

Solution: Always remember to deallocate nodes that are removed from the list in languages without garbage collection.