< Back





19. Remove Nth Node from End of List

This one's a bit annoying because of the possibility of empty list edge cases. The solution requires
you to have a dummy node to handle the event the only node in the list is removed. We solve this by
creating a dummy node to point to the head. Both the slow and fast pointers will start at the dummy
node as well.

We move the fast pointer n + 1 times - n + 1 because the fast pointer is starting at the dummy node.
After this, while the fast pointer is not None, we move both slow and fast pointers in unison. The
fast pointer will reach the end before the slow pointer, and at this point the slow pointer will be
pointing to the node before the node to be removed.

We the unlink the target node, and return dummy.next which will always be the head of the list.

The solution is as follows:


  class Solution:
      def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
          dummy = ListNode(-1)
          dummy.next = head
          slow = fast = dummy

          for _ in range(n + 1):
              fast = fast.next
          
          while fast:
              fast = fast.next
              slow = slow.next

          slow.next = slow.next.next
          return dummy.next


_ Time Complexity:

  O(n) - We traverse all nodes within the linked list.

_ Space Complexity:

  O(1) - We maintain pointers that occupy constant space.