19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example

def removeNthFromEnd(head: Optional[ListNode], n: int):    

    def deleteNodeAfter(d):

        if d is None or d.next is None:

            return

        d.next = d.next.next

       

    first = head    

    for i in range (n-1):

        first = first.next

       

    second = head        

    beforeSecond = None

   

    while first.next:

        beforeSecond = second

        second = second.next

        first = first.next            

   

    if beforeSecond is None:

        return head.next

   

    deleteNodeAfter(beforeSecond)

    return head

   

def removeNthFromEnd_O_N_Space(head: Optional[ListNode], n: int):

                       

    m = {}        

    p = head

    i = 0

    while p:

        m[i] = p

        p = p.next

        i += 1

    L = i

    j = L - n - 1

    if j >= 0:

        deleteNodeAfter(m[j])

        return head

   

    return head.next