✔️ [Python3] ONE PASS, L(・o・)」, Explained
Honestly, it\'s one and a half pass \uD83E\uDD25. So the first half pass we do to find the middle of the list. For that, we use the slow and fast pointers techn
Honestly, it\'s one and a half pass \uD83E\uDD25. So the first half pass we do to find the middle of the list. For that, we use *the slow and fast pointers* technic. The slow one moves one node at a time, and the fast one - two nodes at a time. When the fast one riches the end of the list, the slow one points to the middle point of the list. \n\nFrom the found middle node, we start our second half pass. We detach the left part of the list from the right part and reverse the right part so that the tail would become a head of the right part: `head0 -> head1 -> ...  x  ... <- tail1 <- tail0`\n\nNow we do the third half pass. We iterate over two resulting lists at the same time, and connect nodes as asked in the problem: `head0 -> tail0 -> head1 -> tail1 -> ...`.\n\nTime: **O(n)** - linear for scan\nSpace: **O(1)** - store nothing\n\nRuntime: 84 ms, faster than **94.16%** of Python3 online submissions for Reorder List.\nMemory Usage: 23.2 MB, less than **94.94%** of Python3 online submissions for Reorder List.\n\n```\nclass Solution:\n    def reorderList(self, head: Optional[ListNode]) -> None:\n        if not head.next or not head.next.next:\n            return\n        \n        # search for the middle\n        slow, fast = head, head\n        while fast.next and fast.next.next:\n            slow = slow.next\n            fast = fast.next.next\n\n        tail, cur = None, slow.next\n        slow.next = None # detach list on the middle\n        \n        # reverse right part\n        while cur:\n            cur.next, tail, cur = tail, cur, cur.next\n        \n\t\t# rearrange nodes as asked\n        headCur, headNext = head, head.next\n        tailCur, tailNext = tail, tail.next\n        while True:\n            headCur.next, tailCur.next = tailCur, headNext\n             \n            if not tailNext:\n                return\n            \n            tailCur, headCur = tailNext, headNext\n            tailNext, headNext = tailNext.next, headNext.next\n```
['Python3']