"""19. Remove Nth Node From End of List
Medium

URL: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

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

Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.

Follow up:
Could you do this in one pass?
"""

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val):
        self.val = val
        self.next = None


class SolutionTwoPassesGetSize(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode

        Time complexity: O(n).
        Space complexity: O(1).
        """
        # If no node will be removed.
        if n == 0:
            return head

        # Get the size of the linked list.
        size = 0
        current = head
        while current:
            size += 1
            current = current.next

        # If the head is removed.
        if n == size:
            return head.next

        # Arrive at the (N-1)th node.
        pos = -1
        previous = None
        current = head
        while pos < size - n - 1:
            pos += 1
            previous = current
            current = current.next

        # If the Nth node exists, replace the Nth node by the (N+1)th,
        # and return head.
        if current:
            previous.next = previous.next.next

        return head


class SolutionOnePass(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode

        Time complexity: O(n).
        Space complexity: O(1).
        """
        # If no node will be removed.
        if n == 0:
            return head

        # Track current & previous nodes with distance n.
        # Move iteratively both nodes to the end.
        current_pos = 0
        previous_pos = current_pos - n

        previous = None
        current = head

        while current.next:
            current_pos += 1
            previous_pos += 1

            current = current.next

            if previous_pos == 0:
                previous = head
            elif previous_pos > 0:
                previous = previous.next

        # It previous_pos < 0, it means head will be removed.
        # Else, remove the Nth node.
        if previous_pos < 0:
            return head.next
        else:
            previous.next = previous.next.next
            return head


def main():
    # Solution = SolutionTwoPassesGetSize
    Solution = SolutionOnePass

    # Given linked list: 1->2->3->4->5, and n = 2. Ans: 5.
    # Remove the 2nd node from the end: 1->2->3->5.
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    print Solution().removeNthFromEnd(head, 2).next.next.next.val

    # Remove the 5th node from the end: 2->3->4->5. Ans: 2.
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    print Solution().removeNthFromEnd(head, 5).val

    # Remove the 0th node from the end: 1->2->3->4->5. Ans: 1.
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    print Solution().removeNthFromEnd(head, 0).val


if __name__ == '__main__':
    main()

@@ -745,34 +745,65 @@
 e complexity: O(
-n)
+m), where m is the length of list
 .%0A        Space 
@@ -1763,18 +1763,49 @@
 xity: O(
-n)
+m), where m is the length of list
 .%0A      
@@ -1938,546 +1938,406 @@
   # 
-Track current & previous nodes with distance n.%0A        # Move iteratively both nodes to the end.%0A        current_pos = 0%0A        previous_pos = current_pos - n%0A%0A        previous = None%0A        current = head%0A%0A        while current.next:%0A            current_pos += 1%0A            previous_pos += 1%0A%0A            current = current.next%0A%0A            if previous_pos == 0:%0A                previous = head%0A            elif previous_pos %3E 0:%0A                previous = previous.next%0A%0A        # It previous_pos %3C 0, it means head will be removed.
+Apply Two Pointers: fast and slow.%0A        fast = head%0A        slow = head%0A        previous = ListNode(None)%0A%0A        # Move fast n nodes into the list.%0A        for i in range(n):%0A            fast = fast.next%0A%0A        # Move all nodes at the same pace, and stop at the left of nth node.%0A        while fast.next:%0A            fast = fast.next%0A            previous = slow%0A            slow = slow.next%0A
 %0A   
@@ -2347,26 +2347,16 @@
   # 
-Else, r
+R
 emove 
-the N
+n
 th n
@@ -2364,84 +2364,8 @@
 de.%0A
-        if previous_pos %3C 0:%0A            return head.next%0A        else:%0A    
     
@@ -2399,28 +2399,25 @@
 s.next.next%0A
-    
+%0A
         retu
@@ -2565,17 +2565,8 @@
  = 2
-. Ans: 5.
 %0A   
@@ -2850,565 +2850,8 @@
 al%0A%0A
-    # Remove the 5th node from the end: 2-%3E3-%3E4-%3E5. Ans: 2.%0A    head = ListNode(1)%0A    head.next = ListNode(2)%0A    head.next.next = ListNode(3)%0A    head.next.next.next = ListNode(4)%0A    head.next.next.next.next = ListNode(5)%0A    print Solution().removeNthFromEnd(head, 5).val%0A%0A    # Remove the 0th node from the end: 1-%3E2-%3E3-%3E4-%3E5. Ans: 1.%0A    head = ListNode(1)%0A    head.next = ListNode(2)%0A    head.next.next = ListNode(3)%0A    head.next.next.next = ListNode(4)%0A    head.next.next.next.next = ListNode(5)%0A    print Solution().removeNthFromEnd(head, 0).val%0A%0A
 %0Aif 

Refactor two pointers sol