[LeetCode]Reorder List

[LeetCode]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}.

這道題是將一個給定的單鏈表按照某種規則進行重排序，要求是不可以簡單地直接交換結點中的值。

思路很簡單：
1. 定位到單鏈表的中間結點mid，並將mid->next置為空
2. 將mid之後的子鏈表反轉
3. 將mid之前的子鏈表與反轉後的子鏈表歸並，順序是一前一後。

只需要注意邊界值情況即可。
下面貼上代碼：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getMid(ListNode* head){
        if (!head)
            return NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast&&fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    ListNode* getReversed(ListNode* head){
        ListNode* first = new ListNode(0);
        ListNode* p = head;
        while (p){
            ListNode* r = p->next;
            p->next = first->next;
            first->next = p;
            p = r;
        }
        return first->next;
    }

    void reorderList(ListNode *head) {
        if (!head)
            return;
        ListNode* mid = getMid(head);
        ListNode* midPost = mid->next;
        mid->next = NULL;
        midPost = getReversed(midPost);
        ListNode* first = head;
        ListNode* ans = new ListNode(0);
        ListNode* r = ans;
        ListNode *p, *q;
        while (first&&midPost){
            p = first->next;
            q = midPost->next;
            first->next = midPost;
            r->next = first;
            r = midPost;
            first = p;
            midPost = q;
        }
        r->next = p;
    }
};