Leetcode 143：Reorder list

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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}

这个题目可以分为3步进行， 1. 找到middle node 2. reverse the second half 3. interleave merge the left and right list.

class Solution {
private:
    void reverse(ListNode* &head) {
        //base case
        if (head == NULL || head->next == NULL) {
            return;
        }
        ListNode* cur = head;
        ListNode* pre = NULL;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        head = pre;
        return;
    }
    ListNode* interMerge(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (l1 && l2) {
            cur->next = l1;
            cur = l1;
            l1 = l1->next;
            cur->next = l2;
            cur = l2;
            l2 = l2->next;
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return dummy->next;
    }
public:
    void reorderList(ListNode* head) {
        //sanity check
        if (head == NULL || head->next == NULL) return;
        //find mid node
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* mid = slow;
        ListNode* right = mid->next;
        mid->next = NULL;
        ListNode* left = head;
        //reverse the right part
        reverse(right);
        head = interMerge(left, right);
        return;
    }
};