LeetCode #19: Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

The “Remove Nth Node From End of List” problem on LeetCode asks us to remove the nth node from the end of a linked list and return the head of the modified linked list.

We can solve this problem in Python 3 by following these steps:

1. We start by creating two pointers, fast and slow, and initializing them both to point to the head of the linked list.
2. We move the fast pointer n nodes ahead of the slow pointer. This step is important because it helps us determine the node that we need to remove from the linked list.
3. We iterate through the linked list until the fast pointer reaches the end of the linked list. While iterating, we move both the fast and slow pointers one node at a time.
4. Once the fast pointer reaches the end of the linked list, we update the next pointer of the node that comes before the node that we want to remove. This step effectively removes the node from the linked list.
5. Finally, we return the head of the modified linked list.

Here’s the Python 3 code that implements this approach:

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # Creating two pointers and initializing them to the head of the linked list
        fast = slow = head
        
        # Moving the fast pointer n nodes ahead of the slow pointer
        for i in range(n):
            fast = fast.next
        
        # Iterating through the linked list until the fast pointer reaches the end
        prev = None
        while fast:
            fast = fast.next
            prev = slow
            slow = slow.next
        
        # Updating the next pointer of the node that comes before the node that we want to remove
        if prev:
            prev.next = slow.next
            return head
        else:
            return slow.next

In this code, we first create two pointers, fast and slow, and initialize them both to point to the head of the linked list. We then move the fast pointer n nodes ahead of the slow pointer.

We then iterate through the linked list until the fast pointer reaches the end of the linked list. While iterating, we move both the fast and slow pointers one node at a time. Once the fast pointer reaches the end of the linked list, we update the next pointer of the node that comes before the node that we want to remove.

Time and Space Complexity

The time complexity of this approach is O(n), where n is the length of the linked list, because we need to iterate through the linked list twice. The space complexity of this approach is O(1) because we only use a constant amount of extra space to store the pointers.