My C++ code (split, reverse the second half, and merge), 71 ms
The basic idea is to split the list in half, then reverse the second half,  and at last merge them. It is O(n) time, O(1) space. I was also wondering if there i
 The basic idea is to split the list in half, then reverse the second half,  and at last merge them. It is O(n) time, O(1) space. I was also wondering if there is a better solution.\n\n    class Solution {\n    public:\n        void reorderList(ListNode *head) {\n      // use fast/slow points to find the second half of the list       \n                ListNode *head1, *head2;\n                ListNode *preNode, *curNode;\n                \n                if(!head || !(head->next) )\n                {// if the list is empty or only has one element\n                    return;\n                }\n                else\n                {\n                    head1 = head;\n                    head2 = head->next;\n                    \n                    // find the starting point of the second half\n                    while(head2 && head2->next)\n                    {\n                        head1 = head1->next;\n                        head2 = (head2->next)->next;\n                    }\n                    \n                    //reverse the second half\n                    head2 =head1->next; // the head of the second half\n                    head1->next =NULL;\n                    preNode = NULL;\n                    \n                    while(head2)\n                    {\n                        curNode = head2->next;\n                        head2->next = preNode;\n                        preNode= head2;\n                        head2 = curNode;\n                    }\n                    \n                    // merge the first half and the reversed second half\n                    head2 = preNode;\n                    head1 = head;\n                    \n                    while(head2)\n                    {\n                        curNode = head1->next;\n                        head1 = head1->next = head2;\n                        head2 = curNode;\n                    }\n                    \n                    return;\n                }\n            }
[]