Reorder List

LeetCode #143

Description:

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.

Example:

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Idea:

可以找到中间节点，断开，把后半截单链表reverse一下，再合并两个单链表。

Code:

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==NULL || head->next==NULL) return;
        ListNode *slow=head;
        ListNode *fast=head;

        // break from middle 
        while(fast->next!=NULL && fast->next->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }

        ListNode *head2=slow->next;
        slow->next=NULL;

        // reverse the second half list
        head2=reverseList(head2);
        // merge two lists
        mergeTwoList(head, head2);
    }

    void mergeTwoList(ListNode* head1, ListNode* head2){
        ListNode dummy(-1);
        ListNode *curr=&dummy;
        bool flag1=true;
        while(head1!=NULL || head2 !=NULL){
            if(flag1){
                curr->next=head1;
                head1=head1->next;
            }
            else{
                curr->next=head2;
                head2=head2->next;
            }
            curr=curr->next;
            flag1=!flag1;
        }

    }

    ListNode* reverseList(ListNode* head) {
        if(head==NULL || head->next==NULL) return head;

        ListNode *pre=nullptr, *curr=head;
        ListNode *tmp;

        while(curr!=NULL){
            tmp = curr->next;
            curr->next=pre;
            pre=curr;
            curr=tmp;
        }
        return pre;
    }
};