[LeetCode] Reorder List

Reorder List

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}.

解題思路：

這道題比較簡單，弄清楚題意，然後鏈表操作即可。大體思路是，先計算鏈表長度，然後將鏈表一分為二。後半部分鏈表翻轉，然後將兩個鏈表合並。注意一些邊界條件，比如，若鏈表長度為奇數，前一個鏈表多分一個；若為偶數，兩個鏈表一樣多。為簡便起見，分別分配兩個新表頭。代碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==NULL){
            return;
        }
        int len = getListLength(head);
        ListNode* head1 = new ListNode(0);
        ListNode* head2= new ListNode(0); //head2表示後半部分倒轉
        head1->next = head;
        ListNode* p = head1;
        for(int i=(len+1)/2; i>0; i--){
            p=p->next;
        }
        //此時p表示head1前一個節點
        ListNode* q=p->next;
        p->next=NULL;
        //將後半部分翻轉到head2中
        while(q!=NULL){
            p=q->next;
            q->next=head2->next;
            head2->next=q;
            q=p;
        }
        //將兩個鏈表合並
        p=head1->next;
        while(head2->next!=NULL){
            q=head2->next;
            head2->next = q->next;
            q->next=p->next;
            p->next=q;
            p=q->next;
        }
        head=head1->next;
        delete head1;
        delete head2;
    }
    
    int getListLength(ListNode* head){
        int len = 0;
        while(head!=NULL){
            len++;
            head=head->next;
        }
        return len;
    }
};