A concise O(n) time, O(1) in place solution
// O(N) time, O(1) space in total\n    void reorderList(ListNode *head) {\n        if (!head || !head->next) return;\n        \n        // find the middle node:
    // O(N) time, O(1) space in total\n    void reorderList(ListNode *head) {\n        if (!head || !head->next) return;\n        \n        // find the middle node: O(n)\n        ListNode *p1 = head, *p2 = head->next;\n        while (p2 && p2->next) {\n            p1 = p1->next;\n            p2 = p2->next->next;\n        }\n        \n        // cut from the middle and reverse the second half: O(n)\n        ListNode *head2 = p1->next;\n        p1->next = NULL;\n        \n        p2 = head2->next;\n        head2->next = NULL;\n        while (p2) {\n            p1 = p2->next;\n            p2->next = head2;\n            head2 = p2;\n            p2 = p1;\n        }\n        \n        // merge two lists: O(n)\n        for (p1 = head, p2 = head2; p1; ) {\n            auto t = p1->next;\n            p1 = p1->next = p2;\n            p2 = t;\n        }\n        \n        //for (p1 = head, p2 = head2; p2; ) {\n        //    auto t = p1->next;\n        //    p1->next = p2;\n        //    p2 = p2->next;\n        //    p1 = p1->next->next = t;\n        //}\n    }
[]