Remove Nth Node From End of List medium

Problem Statement

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: []

Steps

1. Two Pointers: We'll use two pointers, fast and slow.
2. Initial Gap: Initially, place fast n nodes ahead of slow. This creates a gap of n nodes between them.
3. Iteration: Move both fast and slow one node at a time until fast reaches the end of the list.
4. Node Removal: At this point, slow points to the node before the one that needs to be removed. Remove the node after slow.
5. Edge Case (Empty List or n > Length): Handle cases where the list is empty or n is larger than the list's length.

Explanation

The key idea is to use two pointers to maintain a constant gap between them. By moving them simultaneously, we ensure that when the fast pointer reaches the end, the slow pointer is positioned correctly to remove the nth node from the end.

Code

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

def removeNthFromEnd(head, n):
    """
    Removes the nth node from the end of a linked list.

    Args:
        head: The head of the linked list.
        n: The position of the node to remove (from the end).

    Returns:
        The head of the modified linked list.
    """

    # Handle empty list or n larger than list length
    if not head or n <= 0:
        return head

    dummy = ListNode(0, head) # add dummy node to handle removing head
    fast = dummy
    slow = dummy

    #Move fast pointer n steps ahead
    for _ in range(n + 1):
        fast = fast.next


    #Move both pointers until fast reaches the end
    while fast:
        fast = fast.next
        slow = slow.next

    #Remove the node
    slow.next = slow.next.next


    return dummy.next

Complexity

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