A python solution O(n) time, O(1) space
\n\n    # Splits in place a list in two halves, the first half is >= in size than the second.\n    # @return A tuple containing the heads of the two halves\n   
\n\n    # Splits in place a list in two halves, the first half is >= in size than the second.\n    # @return A tuple containing the heads of the two halves\n    def _splitList(head):\n        fast = head\n        slow = head\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next\n            fast = fast.next\n    \n        middle = slow.next\n        slow.next = None\n    \n        return head, middle\n    \n    # Reverses in place a list.\n    # @return Returns the head of the new reversed list\n    def _reverseList(head):\n    \n      last = None\n      currentNode = head\n    \n      while currentNode:\n        nextNode = currentNode.next\n        currentNode.next = last\n        last = currentNode\n        currentNode = nextNode\n    \n      return last\n    \n    # Merges in place two lists\n    # @return The newly merged list.\n    def _mergeLists(a, b):\n    \n        tail = a\n        head = a\n    \n        a = a.next\n        while b:\n            tail.next = b\n            tail = tail.next\n            b = b.next\n            if a:\n                a, b = b, a\n                \n        return head\n    \n    \n    class Solution:\n    \n        # @param head, a ListNode\n        # @return nothing\n        def reorderList(self, head):\n    \n            if not head or not head.next:\n                return\n    \n            a, b = _splitList(head)\n            b = _reverseList(b)\n            head = _mergeLists(a, b)
['Linked List', 'Python']