From LeetCode 19. Remove Nth Node From End of List with two pointers

Description

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

img

Solution

Use fast and slow pointers, we first let fast move n steps, and then move fast and slow at the same time, until fast points to the end, then delete the node slow points to.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        head_dummy = ListNode()
        head_dummy.next = head

        slow, fast = head_dummy, head_dummy
        while(n!=0): #fast move n steps forward
            fast = fast.next
            n -= 1
        while(fast.next!=None):
            slow = slow.next
            fast = fast.next
        #fast comes to th end，the next node of slow pointer points to is the nth node from end of list
        slow.next = slow.next.next # delete
        return head_dummy.next