143. Reorder List - cocoder39/coco39_LC GitHub Wiki

143. Reorder List

void reorderList(ListNode* head) {
        if (! head || ! head->next) {
            return;
        }
        
        //find the middle
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        //reverse the second half
        ListNode* p = slow->next;
        slow->next = nullptr;
        ListNode* pre = nullptr;
        while (p) {
            ListNode* cur = p;
            p = p->next;
            cur->next = pre;
            pre = cur;
        }
        
        //merge
        ListNode* p1 = head;
        ListNode* p2 = pre;
        while (p2) { //first half is longer than second half
            ListNode* cur = p2;
            p2 = p2->next;
            cur->next = p1->next;
            p1->next = cur;
            p1 = cur->next;
        } 
    }