19. Remove Nth Node From End of List

Description:

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
'''
[1] two pass)

idea::
1. get the length of linked list, let it len
2. delete len-n+1 th node 

code::
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    length=0
    cur=head
    while cur:
        length+=1
        cur=cur.next

    dummy=prev=ListNode(-1,head)
    cur=head
    for i in range(length-n):
        cur=cur.next
        prev=prev.next

    prev.next=cur.next
    return dummy.next
    
-T/C: O(2n)
-S/C: O(1)
'''

'''
[2] one pass)

idea::
1.fast pointer moves n step first
2.while fast: move slow and fast
3. then, fast=> n+len-n moved, slow=> len-n moved
4. len-n th node should be deleted

code::
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    fast=head
    for i in range(n):
        fast=fast.next

    slow=head
    dummy=prev=ListNode(-1,head)
    while fast:
        slow=slow.next
        fast=fast.next
        prev=prev.next
    prev.next=slow.next
    return dummy.next
    
-T/C: O(n)
-S/C: O(1)
'''

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast=head
        for i in range(n):
            fast=fast.next
        
        slow=head
        dummy=prev=ListNode(-1,head)
        while fast:
            slow=slow.next
            fast=fast.next
            prev=prev.next
        prev.next=slow.next
        return dummy.next