initial
I thought of reversing the linked list and removing the node. But we want the original order, not the reveresed list order. So I didnt know so I looked
solution
Actually, if slow and fast pointers keep a distance of n+1, where n is the nth node from the end of linked list that we wanna remove, then when fast pointer reaches the end (i.e. when fast=None), slow pointer is guaranteed to be at the node right before that nth node. Then we just need to do slow.next = slow.next.next to skip that nth node.
# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next=head
fast,slow=dummy,dummy
for i in range(n+1):
fast=fast.next
while fast:
slow,fast=slow.next,fast.next
slow.next=slow.next.next
return dummy.next
complexity
o(n) time
o(1) space
