A much simple O(n) solution with space O(1)


  • 0
    N
    
    class Solution {
    public:
        void reorderList(ListNode* head) {
            if(!head or !head->next)    return;
            ListNode *slow = head,*fast = head;
            while(fast){
                fast = fast->next;
                if(fast){
                    slow = slow->next;
                    fast = fast->next;
                }
            }
            ListNode *first = head;
            ListNode *curr = slow->next,*pre=NULL;
            slow->next = NULL;
            while(curr){
                auto nxt = curr->next;
                curr->next = pre;
                pre = curr;
                curr = nxt;
            }
            ListNode *second = pre;
            ListNode *newhead = NULL,*temp = NULL;
            int l = 0;
            while(first and second){
                l++;
                if(l&1){
                    if(!newhead){
                        newhead = first;
                        temp = first;
                    }else{
                        temp->next = first;
                        temp = temp->next;
                    }
                    first = first->next;
                }else{
                    if(!newhead){
                        newhead = second;
                        temp = second;
                    }else{
                        temp->next = second;
                        temp = temp->next;
                    }
                    second = second->next;
                }
            }
            if(first){
                if(!newhead)    newhead = first;
                else    temp->next = first;
            }
            if(second){
                if(!newhead)    newhead = second;
                else    temp->next = second;
            }
            head = newhead;
        }
    };
    
    

Log in to reply
 

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