Python solution
The algorithm consists of two steps: 1. reverse the second half of the list; 2. Insert the second half of the list into the first half appropriately. \n\nTo ach
The algorithm consists of two steps: 1. reverse the second half of the list; 2. Insert the second half of the list into the first half appropriately. \n\nTo achieve the first step, we initialize a slow pointer `slow` and a fast pointer `fast`, with the `fast` travels twice as fast as the `slow`, so that when `fast` reaches the end of the list, `slow` reaches the middle of the list. Then we can reverse the links between every node to the right of `slow`. \n\nTo achieve the second step, we initialze another pointer `trav = head`. Then we can make `trav` and `fast` both travel to the middle of the list, and in each step, insert `fast` between `trav` and `trav.next`.\n\nWe illustrate with two examples. Consider first the following list with even length:\n```\n1 -> 2 -> 3 -> 4 (before step 1)\n1 -> 2 -> 3 <- 4 (after step 1, before step 2)\n1 -> 4 -> 2 -> 3 (after step 2)\n```\nNext, consider the following list with odd length:\n```\n1 -> 2 -> 3 -> 4 -> 5 (before step 1)\n1 -> 2 -> 3 <- 4 <- 5 (after step 1, before step 2)\n1 -> 4 -> 2 -> 5 -> 3 (after step 2)\n```\n\nTime complexity: `O(n)`, space complexity: `O(1)`.\n\n```\nclass Solution:\n    def reorderList(self, head):\n        """\n        :type head: ListNode\n        :rtype: void Do not return anything, modify head in-place instead.\n        """\n        if not head or not head.next:\n            return\n        slow = head\n        fast = head.next\n        while fast.next and fast.next.next:\n            slow = slow.next\n            fast = fast.next.next\n        slow = slow.next\n        if fast.next:\n            fast = fast.next\n            \n        # reverse the second half of the list\n        prev = slow\n        curr = slow.next\n        prev.next = None\n        while curr:\n            tmp = curr.next\n            curr.next = prev\n            prev = curr\n            curr = tmp\n            \n        # turn the list into zigzag manner\n        trav = head\n        while fast.next:\n            tmp1 = trav.next\n            tmp2 = fast.next\n            trav.next = fast\n            fast.next = tmp1\n            trav = tmp1\n            fast = tmp2\n```
[]