My O(n) C++ Method, accepted
Firstly, I split the list from the middle into two lists. One from head to middle, and the other from middle to the end. Then we reverse the second list. Finall
Firstly, I split the list from the middle into two lists. One from head to middle, and the other from middle to the end. Then we reverse the second list. Finally we merge these two lists. O(n) time complexity and O(1) space complexity. \n\n    /**\n     * Definition for singly-linked list.\n     * struct ListNode {\n     *     int val;\n     *     ListNode *next;\n     *     ListNode(int x) : val(x), next(NULL) {}\n     * };\n     */\n    class Solution {\n    public:\n        void reorderList(ListNode *head) {\n            if(head == NULL || head->next == NULL || head->next->next==NULL)\n                return;\n            //find the middle of the list, and split into two lists.    \n            ListNode *p=head,*q=head;\n            while(p && q && q->next && q->next->next){\n                p=p->next;\n                q=q->next->next;\n            }\n            \n            ListNode *mid = p->next;\n            p->next=NULL;\n            p=head;\n            //reverse from the middle to the end\n            ListNode *q1=mid, *q2,*q3;\n            if(mid->next){\n                q1=mid;\n                q2=mid->next;\n                while(q2){\n                    q3=q2->next;\n                    q2->next=q1;\n                    q1=q2;\n                    q2=q3;\n                    \n                }\n                mid->next=NULL;\n            }\n            q=q1;\n            //merge these two list\n            ListNode *s=p;\n            p=p->next;\n            while(p && q){\n               s->next=q;\n               s=s->next;\n               q=q->next;\n               \n               s->next=p;\n               s=s->next;\n               p=p->next;\n            }\n            if(p){\n                s->next=p;\n            }\n            if(q){\n                s->next=q;\n            }\n        }\n    };
[]