[C++] O(n) time, O(1) space solution
First Split the list in half.\n2. Reverse the second linked list.\n3. Merge two lists together.\n\n\nclass Solution {\npublic:\n    void reorderList(ListNode* h
1. First Split the list in half.\n2. Reverse the second linked list.\n3. Merge two lists together.\n\n```\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        if(!head) return;\n        \n        // Cut the list in half\n        ListNode* head2 = cutInHalf(head);\n        \n        // Reverse the second part of the list\n        head2 = reverse(head2);\n        \n        // Merge two list\n        merge(head, head2);\n    }\n    \n    ListNode* cutInHalf(ListNode* head) {\n        ListNode* slow = head;\n        ListNode* fast = head;\n        \n        while(fast->next && fast->next->next) {\n            slow = slow->next;\n            fast = fast->next->next;\n        }\n        \n        // Cut in half\n        ListNode* mid = slow->next;\n        slow->next = NULL;\n        \n        return mid;\n    }\n    \n    ListNode* reverse(ListNode* head) {\n        if(!head) return NULL;\n        \n        ListNode* curr = head;\n        ListNode* temp = head;\n        ListNode* prev = NULL;\n        \n        while(curr) {\n            temp = curr->next;\n            curr->next = prev;\n            prev = curr;\n            curr = temp;\n        }\n        return prev;\n    }\n    \n    \n    void merge(ListNode* p, ListNode* q) {\n        if(!p) return;\n        if(!q) return;\n        \n        while(p && q) {\n            ListNode* pTemp = p->next;\n            ListNode* qTemp = q->next;\n            p->next = q;\n            p = pTemp;\n            q->next = p;\n            q = qTemp;\n        }\n    }\n};\n```
['C']