Problem Statement

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

Additional information

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

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]

Brute Force (Two Pass)

Intuition

To remove the nth node from the end, we first need to know the length of the list L. Once we know the length, the problem simplifies to removing the (L - n + 1)th node from the beginning.

Algorithm

1. Traverse the list to calculate the total length L.
2. If n == L, it means we need to remove the head. Return head.next.
3. Traverse the list again to find the node just before the target node (index L - n - 1).
4. Update the next pointer of that node to skip the target node.

def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next
        
    if length == n:
        return head.next
        
    curr = head
    # Move to the node right before the one we want to delete
    for _ in range(length - n - 1):
        curr = curr.next
        
    curr.next = curr.next.next
    return head

Time & Space Complexity

• Time complexity: O(L)

• Reason: We traverse the list twice: once to find the length and once to find the node.

• Space complexity: O(1)

• Reason: We only use a few variables for pointers and length.

One Pass (Two Pointers)

Intuition

We can solve this in a single pass using two pointers, left and right. If we create a gap of n nodes between right and left, and then move both pointers forward until right reaches the end, left will naturally be at the node right before the target.

Using a dummy node simplifies edge cases, such as removing the head itself (e.g., list [1], n=1).

Algorithm

1. Create a dummy node pointing to head.
2. Initialize left = dummy and right = head.
3. Move right forward n times. This creates the gap.
4. Move both left and right forward simultaneously until right reaches the end (becomes None).
5. Now left.next is the node to be removed. Update left.next = left.next.next.
6. Return dummy.next.

def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    left = dummy
    right = head
    
    # Move right n steps ahead
    while n > 0 and right:
        right = right.next
        n -= 1
        
    # Move both pointers until right reaches the end
    while right:
        left = left.next
        right = right.next
        
    # Delete the node
    left.next = left.next.next
    
    return dummy.next

Time & Space Complexity

• Time complexity: O(L)

• Reason: We traverse the list exactly once.

• Space complexity: O(1)

• Reason: We only use constant extra space for pointers.