143. Reorder List

https://leetcode.com/problems/reorder-list/

Solution:
May use two pointers, one is fast that move two nodes per time and the other is slow that move one per time. Then when the fast one reaches the end, the slow one reaches the middle. The next step is to divide the list into two lists: the first half and the second half. Reverse the second half, then merge them. (Seems not hard to understand, I think this question is designed for checking the details for implementation.)

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        ListNode *fast = head, *slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = reverseL(slow->next);
        slow->next = NULL; //must have!
        slow = head;
        while(slow && fast){
            ListNode *t = fast;
            fast = t->next;
            t->next = slow->next;
            slow->next = t;
            slow = t->next;
        }
    }
private:
    ListNode* reverseL(ListNode* h){
        if(!h || !h->next) return h;
        ListNode *dummy = new ListNode(-1);
        dummy->next = h;
        while(h && h->next){
            ListNode* p = h->next;
            h->next = p->next;
            p->next = dummy->next;
            dummy->next = p;
        }
        return dummy->next;
    }
};