[VIDEO] Visualization of Two-Pointer Solution (One Pass)
https://www.youtube.com/watch?v=mGTeaxlg69s\n\nThis problem would be a lot easier if n was given in terms of nodes from the front of the list.  Then we could si
https://www.youtube.com/watch?v=mGTeaxlg69s\n\nThis problem would be a lot easier if `n` was given in terms of nodes from the <i>front</i> of the list.  Then we could simply traverse the list and stop at the `n-1` node, and make that node skip node `n`.\n\nThe challenge is that since `n` is given in terms of nodes from the <i>end</i> of the list, while we\'re traversing the list, we have no idea when to stop (since we don\'t know the length of the list until we traverse it completely).  Then once we\'re at the end of the list, we would like to now go <i>back</i> `n` nodes, but since this is a singly linked list, there is no way to traverse backwards. And now we\'re stuck.\n\nThe solution is to use two pointers, `fast` and `slow`.  `fast` will get a head start of `n` nodes, and then we\'ll move up both pointers until `fast` reaches the end of the list.  Then at that point, `slow` will be perfectly positioned `n` nodes behind `fast`, and we can use `slow` to make node `n-1` skip node `n` (please see the video for a visualization of this).\n\nIn the worst case, each pointer will traverse the entire list once, so this runs in <b>O(n) time</b>.  We will also only ever need 2 extra pointers, so this also runs in <b>O(1) space</b>.\n\n# Code\n```\n# Definition for singly-linked list.\n# class ListNode:\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution:\n    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n        fast = head\n        slow = head\n        for i in range(n):\n            fast = fast.next\n        \n        if not fast:\n            return head.next\n        \n        while fast.next:\n            fast = fast.next\n            slow = slow.next\n        \n        slow.next = slow.next.next\n        return head\n        \n\n```
['Linked List', 'Two Pointers', 'Python', 'Python3']