Solutions

# Two pointers. Dummy (sentinel) node for edge cases (head removal). Left pointer should stop 1 node before the one to remove.
# linked-list,two-pointers

# Two pointers: O(n) time, O(1) space
def removeNthFromEnd(head: ListNode | None, n: int) -> ListNode | None:
    dummy = ListNode(-1)
    dummy.next = head
    cur = dummy
    for _ in range(n):
        cur = cur.next

    left = cur
    right = dummy
    while left and left.next:
        left = left.next
        right = right.next

    right.next = right.next.next
    return dummy.next


# Recursion: O(n) time, O(n) space
def rec(head, n):
    if not head:
        return None

    head.next = rec(head.next, n)
    n[0] -= 1
    if n[0] == 0:
        return head.next
    return head

def removeNthFromEnd(head, n):
    return rec(head, [n])


# Brute force, array: O(n) time, O(n) space
def removeNthFromEnd(head: ListNode | None, n: int) -> ListNode | None:
    nodes = []
    cur = head
    while cur:
        nodes.append(cur)
        cur = cur.next

    removeIndex = len(nodes) - n
    if removeIndex == 0:
        return head.next

    nodes[removeIndex - 1].next = nodes[removeIndex].next
    return head


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