sundeepblue
3/19/2014 - 8:16 PM

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes'

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes' values. For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

Reorder List.cpp
content_copyfile_download
void reorderList(ListNode *head) {
    if(!head || !head->next) return;
    
    // step1: get middle node and its previous node, cut to 2 halves.
    ListNode *p = head, *q = head, *tail = NULL; // cannot write *q=head->next
    while(q && q->next) {             
        tail = p;
        p = p->next;
        q = q->next->next;
    }
    tail->next = NULL;  // gist1
    
    // step2: reverse the 2nd half
    ListNode *pre = NULL, *cur = p;
    while(cur) {
        ListNode *nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    
    // step3: merge the 2 halves
    ListNode *right_half = pre;
    ListNode *p1 = head, *p2 = right_half;
    bool use_left = false;  // gist2
    while(p1 && p2) {
        if(use_left == false) {
            ListNode *nxt = p1->next;
            p1->next = p2;
            p1 = nxt;
        }
        else if(use_left == true) {
            ListNode *nxt = p2->next;
            p2->next = p1;
            p2 = nxt;
        }
        use_left = !use_left;
    }
}