# LeetCode - 0143. Reorder List
### 題目網址：https://leetcode.com/problems/reorder-list/
###### tags: `LeetCode` `Medium` `連結串列（Linked List）` `模擬`

/*
    -LeetCode format-
    Problem: 143. Reorder List
    Difficulty: Medium
    
    by Inversionpeter
*/



/**
 * 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) {}
 * };
 */

static const auto Initialize = []{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    return nullptr;
}();

ListNode* ReverseList(ListNode *head) {
    ListNode *last = head, *now = head->next, *next;
    while (now) 
        next = now->next, now->next = last, last = now, now = next;
    head->next = nullptr;
    return last;
}

ListNode* FindMiddle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *first = head, *second = ReverseList(FindMiddle(head)), *buffer;
        while (first->next != second && first != second) {
            buffer = first->next;
            first->next = second;
            first = buffer;
            buffer = second->next;
            second->next = first;
            second = buffer;
        }
    }
};