Remove Nth Node From End of List

Problem

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

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]

Constraints:

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

Follow up: Could you do this in one pass?

Solution

Approach: Two Pointers (One Pass)

The key insight is to use two pointers separated by n nodes. When the fast pointer reaches the end, the slow pointer will be at the node before the one to remove.

Algorithm:

Use a dummy node to handle edge cases (removing head)
Place fast pointer n steps ahead of slow pointer
Move both pointers until fast reaches the end
Remove the target node by adjusting slow pointer’s next

Implementation

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow = dummy
        fast = 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:
            slow = slow.next
            fast = fast.next

        # Remove the nth node from end
        slow.next = slow.next.next

        return dummy.next

Alternative (Without Dummy Node):

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # First pass: get length
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next

        # Edge case: removing head
        if length == n:
            return head.next

        # Second pass: find node before target
        curr = head
        for _ in range(length - n - 1):
            curr = curr.next

        # Remove target node
        curr.next = curr.next.next

        return head

Complexity Analysis

Two Pointers (One Pass):

Time Complexity: O(L), where L is the length of the list. We traverse the list once.
Space Complexity: O(1), we only use a constant amount of extra space.

Two Pass:

Time Complexity: O(L), we traverse the list twice but still linear.
Space Complexity: O(1).

Key Insights

Dummy Node Advantage: Using a dummy node simplifies edge cases, especially when removing the head node. The dummy’s next always points to the actual head.
Gap Maintenance: By keeping the fast pointer n steps ahead, when fast reaches the end (None), slow is positioned exactly before the node to remove.
One Pass Efficiency: The two-pointer technique solves this in one pass without needing to know the list length first.
Pointer Positioning: We want slow to be at the node before the target node, not at the target itself. This allows us to do slow.next = slow.next.next to remove the target.
Edge Case Handling: When n equals the list length, we’re removing the head. The dummy node handles this elegantly: dummy.next becomes the new head.