LC19. Remove Nth Node From End of List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # O(N) space O(1)
        dummy = ListNode()
        dummy.next = head 
        # step1 cnt length
        leng = 0
        p = head
        while p:
            leng += 1 
            p = p.next
        
        if n > leng:
            return None
        # step2:  go to length - n point, remove current node 
        cnt = 0 
        pp = head 
        pre = dummy 
        while cnt < leng-n:
            pre = pp
            pp = pp.next
            cnt += 1
        pre.next = pp.next
        return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # O(N) space O(1)
        dummy = ListNode()
        dummy.next = head 
        fst,snd = dummy,dummy
        for i in range(n+1):# here jump n+1 steps insead of n steps
            fst = fst.next
        
        while fst:
            fst = fst.next
            snd = snd.next
        
        snd.next = snd.next.next
        return dummy.next