Python O(n) by two-pointers [w/ Visualization]
The first method is to reorder by two pointers with the help of aux O(n) space array.\n\nThe second method is to reorder by mid-point finding, linked list rever
The first method is to reorder by **two pointers** with the help of **aux O(n)** space **array**.\n\nThe second method is to reorder by **mid-point finding**, **linked list reverse**, and **linkage update** in O(1) aux space.\n\n---\n\nMethod_#1\n\n**Visualization and Diagram**\n\n![image](https://assets.leetcode.com/users/images/9e0e9d9f-80bd-4e03-bdfa-07dffec9a960_1597916142.2456708.png)\n\n---\n\n**Implementation**:\n\n```\nclass Solution:\n    def reorderList(self, head: ListNode) -> None:\n        """\n        Do not return anything, modify head in-place instead.\n        """\n\t\t\n\t\t# ----------------------------------------------\n\t\t# Save linked list in array\n\t\t\n        arr = []\n        \n        cur, length = head, 0\n\t\t\n        while cur:\n            arr.append( cur )\n            cur, length = cur.next, length + 1\n        \n\t\t# ----------------------------------------------\n        # Reorder with two-pointers\n\t\t\n        left, right = 0, length-1\n        last = head\n        \n        while left < right:\n            arr[left].next = arr[right]\n            left += 1\n            \n            if left == right: \n                last = arr[right]\n                break\n                \n            arr[right].next = arr[left]\n            right -= 1\n            \n            last = arr[left]\n        \n        if last:\n            last.next= None\n```\n\n---\n\nMethod_#2\n\n**Visualization and Diagram**\n\n![image](https://assets.leetcode.com/users/images/e78d2d3a-5217-49f8-87e3-bc59c19070fc_1597916232.8641367.png)\n\n---\n\n![image](https://assets.leetcode.com/users/images/68bc80f5-630e-4c0a-a9da-605196a4e004_1597916252.5191195.png)\n\n---\n\n![image](https://assets.leetcode.com/users/images/391f41fb-ed1f-4d67-a2f9-4d6aaf119214_1597916282.3228247.png)\n\n\n---\n\n**Implementation**:\n\n```\nclass Solution:\n    def reorderList(self, head: ListNode) -> None:\n        """\n        Do not return anything, modify head in-place instead.\n        """\n        \n        if not head:\n            # Quick response for empty linked list\n            return None\n        \n        # ------------------------------------------\n        # Locate the mid point of linked list\n        # First half is the linked list before mid point\n        # Second half is the linked list after mid point\n        \n        fast, slow = head, head\n        \n        while fast and fast.next:\n            slow, fast = slow.next, fast.next.next\n            \n        mid = slow\n        \n        # ------------------------------------------\n        # Reverse second half\n        \n        prev, cur = None, mid\n        \n        while cur:\n            cur.next, prev, cur = prev, cur, cur.next\n        \n        head_of_second_rev = prev\n        \n        # ------------------------------------------\n        # Update link between first half and reversed second half\n        \n        first, second = head, head_of_second_rev\n        \n        while second.next:\n            \n            next_hop = first.next\n            first.next = second\n            first = next_hop\n            \n            next_hop = second.next\n            second.next = first\n            second = next_hop\n```\n\n---
['Linked List', 'Two Pointers', 'Iterator', 'Python', 'Python3']