LeetCode 19 - Remove Nth Node From End of List

This problem asks us to remove the nth node counted from the end of a singly linked list and return the modified list. A singly linked list is a sequence of nodes where each node contains a value and a pointer to the next node.

leetcodemediumlinked-listtwo-pointers

LeetCode Problem 19

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers

Solution

Problem Understanding

This problem asks us to remove the nth node counted from the end of a singly linked list and return the modified list.

A singly linked list is a sequence of nodes where each node contains a value and a pointer to the next node. Unlike arrays, linked lists do not allow direct indexing, so accessing a node at a specific position requires traversing the list step by step.

The input consists of two values:

  • head, which points to the first node of the linked list
  • n, which tells us which node from the end should be removed

The output should be the head of the updated linked list after removing the target node.

For example, if the list is:

1 -> 2 -> 3 -> 4 -> 5

and n = 2, the second node from the end is 4, so the result becomes:

1 -> 2 -> 3 -> 5

The constraints are relatively small, since the list size is at most 30 nodes. Even an O(n²) solution would technically pass. However, the follow-up explicitly asks whether we can solve it in one pass, which strongly suggests that the intended solution uses a more efficient traversal strategy.

Several edge cases are important here.

If the list contains only one node and that node must be removed, the result should be an empty list.

If the node to remove is the head itself, we must correctly update the head pointer. This is a common source of bugs in linked list problems.

If the node to remove is the last node, we must correctly disconnect the tail.

The problem guarantees that 1 <= n <= sz, so we never need to handle invalid values of n.

Approaches

Brute Force Approach

A straightforward solution is to perform two passes over the linked list.

In the first pass, we count the total number of nodes in the list. Once we know the length, we can determine the position of the node that must be removed from the beginning of the list.

If the list length is L, then the node to remove is at position:

L - n

from the start, using zero-based indexing.

We then perform a second traversal to reach the node immediately before the target node and update its next pointer to skip the target.

This approach is correct because counting the total length allows us to precisely convert a position from the end into a position from the start.

Although this solution is perfectly acceptable for the given constraints, it requires two passes through the list. The follow-up asks for a one-pass solution, which motivates a more optimal technique.

Optimal Approach

The key insight is that we do not actually need to know the total length of the list.

Instead, we can maintain a fixed gap of n nodes between two pointers. When the fast pointer reaches the end of the list, the slow pointer will automatically be positioned right before the node that needs to be removed.

This works because the distance between the pointers remains constant throughout the traversal.

To simplify edge cases, especially when removing the head node, we introduce a dummy node before the actual head. The dummy node points to the original head and allows us to treat head removal exactly the same as any other removal operation.

The algorithm proceeds as follows:

  • Move the fast pointer n steps ahead
  • Move both pointers together until the fast pointer reaches the last node
  • The slow pointer now sits immediately before the target node
  • Remove the target by updating slow.next

This achieves the follow-up requirement because the list is traversed only once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Two passes, first counts length, second removes node
Optimal O(n) O(1) One-pass two-pointer solution with fixed gap

Algorithm Walkthrough

  1. Create a dummy node whose next pointer references the original head.

This dummy node simplifies removal logic. Without it, removing the head node would require separate handling because the head pointer itself changes. 2. Initialize two pointers, fast and slow, both starting at the dummy node.

The goal is to maintain a gap of exactly n nodes between them. 3. Move the fast pointer forward n times.

After this step, fast is n nodes ahead of slow. 4. Move both pointers forward together until fast.next becomes None.

At this moment:

  • fast is at the last node
  • slow is immediately before the node that must be removed
  1. Remove the target node by updating:
slow.next = slow.next.next

This bypasses the target node and reconnects the list.

  1. Return dummy.next.

This correctly handles all cases, including when the original head was removed.

Why it works

The algorithm maintains an invariant that the fast pointer is always n nodes ahead of the slow pointer. When fast reaches the final node, slow must therefore be positioned immediately before the node that is n positions from the end. Since linked list removal only requires access to the previous node, slow is exactly where we need it to be.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def removeNthFromEnd(
        self,
        head: Optional[ListNode],
        n: int
    ) -> Optional[ListNode]:
        
        dummy = ListNode(0, head)
        
        fast = dummy
        slow = dummy
        
        # Move fast pointer n steps ahead
        for _ in range(n):
            fast = fast.next
        
        # Move both pointers until fast reaches the end
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        # Remove the target node
        slow.next = slow.next.next
        
        return dummy.next

The implementation begins by creating a dummy node that points to the original head. This avoids special-case logic for deleting the first node.

Both fast and slow pointers start at the dummy node. The fast pointer is advanced n steps ahead so that the required gap is established.

The main traversal loop moves both pointers together while preserving the gap. Once fast.next becomes None, the slow pointer is positioned directly before the node to remove.

The removal itself is performed with a single pointer update:

slow.next = slow.next.next

This skips the target node and reconnects the remaining list.

Finally, dummy.next is returned because the original head may have been removed.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    
    dummy := &ListNode{
        Val:  0,
        Next: head,
    }
    
    fast := dummy
    slow := dummy
    
    // Move fast pointer n steps ahead
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    
    // Move both pointers together
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    
    // Remove target node
    slow.Next = slow.Next.Next
    
    return dummy.Next
}

The Go implementation follows exactly the same logic as the Python solution. The primary difference is explicit pointer syntax.

Go uses nil instead of Python's None, and struct pointers are manipulated directly using *ListNode.

Memory management is handled automatically by Go's garbage collector, so the removed node does not need explicit deallocation.

Worked Examples

Example 1

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

Initial list:

dummy -> 1 -> 2 -> 3 -> 4 -> 5

After moving fast forward 2 steps:

Step fast slow
Start dummy dummy
Move 1 1 dummy
Move 2 2 dummy

Now move both pointers together:

Iteration fast slow
1 3 1
2 4 2
3 5 3

At this point, fast.next is None, so stop.

slow is at node 3, which is immediately before node 4.

Perform removal:

3.next = 5

Final list:

1 -> 2 -> 3 -> 5

Example 2

Input: head = [1], n = 1

Initial list:

dummy -> 1

Move fast one step:

Step fast slow
Start dummy dummy
Move 1 1 dummy

Since fast.next is None, the loop does not execute.

slow remains at the dummy node.

Removal:

dummy.next = None

Final list:

[]

Example 3

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

Initial list:

dummy -> 1 -> 2

Move fast one step:

Step fast slow
Start dummy dummy
Move 1 1 dummy

Move both pointers:

Iteration fast slow
1 2 1

Now fast.next is None.

slow points to node 1, which is immediately before node 2.

Removal:

1.next = None

Final list:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited at most once
Space O(1) Only a few pointer variables are used

The algorithm performs a single traversal of the linked list. Even though two pointers move through the structure, each pointer only advances forward and never revisits nodes, so the total work remains linear in the number of nodes.

The space complexity is constant because no auxiliary data structures proportional to input size are allocated.

Test Cases

# Helper functions for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy
    
    for value in values:
        current.next = ListNode(value)
        current = current.next
    
    return dummy.next

def list_to_array(head):
    result = []
    
    while head:
        result.append(head.val)
        head = head.next
    
    return result

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0, head)
        
        fast = dummy
        slow = dummy
        
        for _ in range(n):
            fast = fast.next
        
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next
        
        return dummy.next

solution = Solution()

# Example 1
head = build_list([1, 2, 3, 4, 5])
result = solution.removeNthFromEnd(head, 2)
assert list_to_array(result) == [1, 2, 3, 5]  # remove middle node

# Example 2
head = build_list([1])
result = solution.removeNthFromEnd(head, 1)
assert list_to_array(result) == []  # remove only node

# Example 3
head = build_list([1, 2])
result = solution.removeNthFromEnd(head, 1)
assert list_to_array(result) == [1]  # remove tail node

# Remove head from larger list
head = build_list([1, 2, 3])
result = solution.removeNthFromEnd(head, 3)
assert list_to_array(result) == [2, 3]  # remove head

# Remove tail from longer list
head = build_list([10, 20, 30, 40])
result = solution.removeNthFromEnd(head, 1)
assert list_to_array(result) == [10, 20, 30]  # remove last node

# Remove second node
head = build_list([5, 6, 7, 8])
result = solution.removeNthFromEnd(head, 3)
assert list_to_array(result) == [5, 7, 8]  # remove internal node

# Two-node list removing first node
head = build_list([1, 2])
result = solution.removeNthFromEnd(head, 2)
assert list_to_array(result) == [2]  # remove head in small list

# Larger sequential list
head = build_list(list(range(1, 11)))
result = solution.removeNthFromEnd(head, 5)
assert list_to_array(result) == [1, 2, 3, 4, 5, 7, 8, 9, 10]  # remove middle element

print("All test cases passed!")
Test Why
[1,2,3,4,5], n=2 Standard middle-node removal
[1], n=1 Single-node edge case
[1,2], n=1 Tail removal
[1,2,3], n=3 Head removal
[10,20,30,40], n=1 Removing last node in longer list
[5,6,7,8], n=3 Internal node removal
[1,2], n=2 Removing head in minimal multi-node list
[1..10], n=5 Larger traversal validation

Edge Cases

One important edge case occurs when the head node itself must be removed. This happens when n equals the length of the list. Without a dummy node, the implementation would need special logic to update the head pointer separately. The dummy node eliminates this complication because the node before the head always exists.

Another critical case is a single-node list. For example:

[1], n = 1

After removal, the list becomes empty. A careless implementation might attempt to access next pointers that no longer exist. The current solution handles this safely because the dummy node remains valid even when the real list becomes empty.

Removing the tail node is also a common source of mistakes. In a singly linked list, there is no backward traversal, so we must stop at the node immediately before the tail. The two-pointer gap guarantees that the slow pointer lands exactly at that location, making tail removal straightforward.

A final subtle edge case involves very small lists, especially two-node lists. Pointer movement logic can easily become off by one in these scenarios. Using the invariant that fast stays exactly n nodes ahead of slow ensures the algorithm behaves consistently regardless of list size.