# 【LeetCode】 143. Reorder List

## Description
> Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

> You may not modify the values in the list's nodes, only nodes itself may be changed.

> 給予一個單向串列鏈結L: L0→L1→…→Ln-1→Ln,
請重新排列為: L0→Ln→L1→Ln-1→L2→Ln-2→…

> 你不應該改變鏈結中節點的值，只應該改變節點之間的連結。

## Example:

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.


Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

## Solution

* 我先將這題按照直覺做，每次找到倒數第二個節點，將它的下一個節點拉回前面插入，並且將它的`next`設為`NULL`。
* 結果吃了TLE，仔細想想每次要找到最後一個節點，都要跑整段鏈結，十分耗時。
---
* 重新思考之後，我將這題分為三個部分：
* 切半
* 反轉
* 插入
* 我們要做的事情是將後半段放入前半段，但順序要反過來，所以我們要先切半和反轉。
* 切半的部分和[這題](https://hackmd.io/@Zero871015/LeetCode-876)一樣，而反轉和[這題](https://hackmd.io/@Zero871015/LeetCode-206)一樣，因此請先做過這兩題，這邊故跳過。
* 得到切半和插入後就簡單啦，將後半的鏈結拿出第一個元素，插到前半鏈結，然後往下移一個，一直到鏈結跑完就好了。
* 下面code有個`move`，那是因為我的切半其實沒有寫好，前半會多一個節點，因此我需要記錄下來並適時將它移除。

### Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* clipHalf(ListNode* head)
    {
        ListNode* one = head;
        ListNode* two = head;
        while(two && two->next)
        {
            one = one->next;
            two = two->next;
            if(two)
                two = two->next;
        }
        return one;
    }
    
    ListNode* reverse(ListNode* head)
    {
        ListNode* next = head->next;
        ListNode* newHead = head;
        ListNode* pre = NULL;
        
        while(next)
        {
            pre = newHead;
            newHead = next;
            next = newHead->next;
            newHead->next = pre;
        }
        head->next = NULL;
        return newHead;
    }
    
    void reorderList(ListNode* head) {
        if(!head || !head->next || !head->next->next)
            return;
        ListNode* half = clipHalf(head);
        ListNode* move = half;
        half = reverse(half);
        
        ListNode* tempA;
        ListNode* tempB;
        while(head && half)
        {
            if(half->next == move)
                half->next = NULL;
            tempA = head->next;
            tempB = half->next;
            head->next = half;
            half->next = tempA;
            head = tempA;
            half = tempB;
        }
    }
};

###### tags: `LeetCode` `C++`