# 143-Reorder List
###### tags: `Medium`
## Question
https://leetcode.com/problems/reorder-list/
## Key
1. Find the middle node
2. Partition th list into two lists
3. Reverse the second one
4. Use a loop for iterating two lists to update the next node in turn
## Reference
## Solution

void reorderList(ListNode* head) {
   if(head == nullptr) return;

   ListNode *slow = head;
   ListNode *fast = head->next;
   while(fast != nullptr && fast->next != nullptr){
       slow = slow->next;
       fast = fast->next->next;
   }

   ListNode *middle = slow->next;
   ListNode *right = reverseList(slow->next);
   slow->next = nullptr;
   head = mergeTwoList(head, right);
}

ListNode *mergeTwoList(ListNode *left, ListNode *right){
   ListNode *dummy = new ListNode(-1);
   ListNode *cur = dummy;
   bool flag = true;
   while(left != nullptr && right != nullptr){
       if(flag){
           cur->next = left;
           left = left->next;
       }else{
           cur->next = right;
           right = right->next;
       }

       flag = !flag;
       cur = cur->next;
   }

   while(left != nullptr){
       cur->next = left;
       cur = cur->next;
       left = left->next;
   }

   while(right != nullptr){
       cur->next = right;
       cur = cur->next;
       right = right->next;
   }

   return dummy->next;
}

ListNode *reverseList(ListNode *root){
    ListNode *pre = nullptr;
    ListNode *cur = root;
    while(cur != nullptr){
        ListNode *temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }

    return pre;
}