19. Remove Nth Node From End of List

Problem Description

Given the head of a linked list, remove the n<sup>th</sup> node from the end of the list and return its head.

Solution: Two Pointers

This problem can be efficiently solved using the two-pointer technique. We'll use two pointers, fast and slow, both initially pointing to a dummy node prepended to the head of the list. This dummy node simplifies handling the case where the first node needs to be removed.

1. Initialization: Create a dummy node and set fast and slow to point to it.
2. Move fast: Move the fast pointer n steps forward. This creates a gap of n nodes between fast and slow.
3. Move together: Move both fast and slow pointers one step at a time until fast reaches the end of the list. At this point, slow will be pointing to the node before the nth node from the end.
4. Remove the node: Remove the nth node from the end by setting slow.next to slow.next.next.
5. Return: Return the next pointer of the dummy node (the head of the modified list).

Time and Space Complexity

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

Code Implementation (Python)

# 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 = ListNode(next=head)  # Dummy node simplifies edge cases
        fast = slow = dummy
        
        # Move fast pointer n steps ahead
        for _ in range(n):
            fast = fast.next
            if fast is None: #Handle edge case where n is larger than list length
                return head
 
        # Move both pointers until fast reaches the end
        while fast.next:
            fast = fast.next
            slow = slow.next
 
        # Remove the nth node from the end
        slow.next = slow.next.next
 
        return dummy.next  # Return the head of the modified list
 

The implementations in other languages (Java, C++, Go, TypeScript, Rust, Javascript, Swift, Ruby, C#, PHP) follow the same logic, differing only in syntax and data structures. The core algorithm remains consistent. Refer to the original response for the complete code examples in these languages.