Remove nth element from end

2 solutions

The idea of the first solution is:

1) Compute the linked list length

2) Go to the node just before the nth element from end

3) Link it to the n-1th element from end

# Solution 1
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    # first we compute the length of the linked list
    curr, list_len = head, 0
    while curr:
        curr = curr.next
        list_len += 1
        
    # to is the (list_len - n - 1) node, ie the node right before the (list_len - n) node, the node to remove
    to = list_len - n - 1

    # if to is negative, the element to remove is the first one and hence returning head.next will remove it
    if to<0:
        return(head.next)

    # otherwise go to the (list_len - n - 1) node 
    curr, i = head, 0
    for i in range(to):
        curr = curr.next

    # link the (list_len - n - 1) node to its grandchildren ie its next.next element
    curr.next = curr.next.next
    return(head)

The idea of the second solution is:

1) Create two head slow and fast

2) Advance fast of n nodes

3) If fast is None (ie fast is at the end), hence the list is exactly of length n and the node to remove is the first one

4) Otherwize advance fast and slow until fast reaches end. As slow is n nodes backward from fast it stops at the node right before the one to remove. Link this node to its grandchildren

# Solution 2
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    fast = slow = head
    # advance fast of n nodes
    for _ in range(n):
        fast = fast.next
        
    # if fast is None hence the nth element from end is the first element
    if not fast:
        return head.next
    
    # advance fast and slow until fast reaches end. As slow is n nodes backward from fast it stops at the right node
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return head