[Python] 2 solutions: Stack, 3 steps - Clean & Concise
\u2714\uFE0F Solution 1: Using Stack\n- The idea is that we use stack to store all nodes in the linked list. Then the top of the stack is the last node.\n- Iter
**\u2714\uFE0F Solution 1: Using Stack**\n- The idea is that we use stack to store all nodes in the linked list. Then the top of the stack is the last node.\n- Iterate `len(st) // 2` times, link in order:\n\t- `nxt = head.next`\n\t- `head -> st.pop() -> nxt`\n\t- `head = nxt`.\n![image](https://assets.leetcode.com/users/images/63f8929c-1345-4c13-b711-ba1659a10637_1632724494.2345262.png)\n\n```python\nclass Solution:\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        """\n        Do not return anything, modify head in-place instead.\n        """\n        st = []\n        cur = head\n        while cur != None:\n            st.append(cur)\n            cur = cur.next\n            \n        for i in range(len(st) // 2):\n            nxt = head.next\n            head.next = st.pop()\n            head = head.next\n            head.next = nxt\n            head = head.next\n            \n        if head != None:\n            head.next = None\n```\nComplexity:\n- Time: `O(N)`, where `N <= 5 * 10^4` is number of nodes in the linked list.\n- Space: `O(N)`\n\n---\n**\u2714\uFE0F Solution 2: 3 steps**\n- Step 1: Find the middle of the linked list then cut the middle into 2 halfs.\n- Step 2: Reverse the last half of the linked list.\n- Step 3: Merge 2 list one by one.\n```python\nclass Solution:\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        """\n        Do not return anything, modify head in-place instead.\n        """\n        def findMiddle(head):  # return mid, prevMid\n            prevSlow = None\n            slow = fast = head\n            while fast != None and fast.next != None:\n                prevSlow = slow\n                slow = slow.next\n                fast = fast.next.next\n            return slow, prevSlow\n        \n        def reverse(head):\n            newHead = None\n            while head != None:\n                nxt = head.next\n                head.next = newHead\n                newHead = head\n                head = nxt\n            return newHead\n        \n        def mergeOneByOne(head1, head2):\n            dummyNode = curHead = ListNode(0)\n            while head1 != None and head2 != None:\n                curHead.next = head1\n                curHead = curHead.next\n                head1 = head1.next\n                    \n                curHead.next = head2\n                curHead = curHead.next\n                head2 = head2.next\n                \n            if head1 != None:\n                curHead.next = head1\n            elif head2 != None:\n                curHead.next = head2\n                \n            return dummyNode.next\n        \n        \n        # Step 1: Find the middle of the linked list and cut the middle into 2 halfs\n        mid, prevMid = findMiddle(head)\n        if prevMid == None: return head  # Case one element\n        prevMid.next = None  # cut the middle into 2 halfs\n        \n        # Step 2: Reverse the last half of the linked list\n        half = reverse(mid)\n        \n        # Step 3: Merge 2 list one by one\n        return mergeOneByOne(head, half)\n```\nComplexity:\n- Time: `O(N)`, where `N <= 5 * 10^4` is number of nodes in the linked list.\n- Space: `O(1)`
[]