Simple yet best solution in C++


  • -1
    class Solution {
    public:
        void reorderList(ListNode* head) 
        {
            if(!head || !head->next) return ;
            ListNode newHead(0), *slow = head, *fast = head->next;
            ListNode *p = head, *next = NULL, *t = NULL;
            while(fast && fast->next) //start to split it into two halves, the right should be less than the left;
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            newHead.next = slow->next;
            slow->next = NULL;
            p = newHead.next->next; //start to reverse;
            t = &newHead;
            t->next->next = NULL;
            while(p)
            {
                next = p->next;
                p->next = t->next;
                t->next = p;
                p = next;
            }
            fast = newHead.next, p = head; //start to merge;
            while(p)
            {
                next = p->next;
                t = fast->next;
                fast->next = p->next;
                p->next = fast;
                if(!t) return ;
                fast = t;
                p = next;
            }
            return ;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.