Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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}.

思路:(1)将链表从中间分开； (2)将后半部分反转； (3)再将反转后的后半部分合并到前半部分中。

/**
 * 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 || !head->next)    return;
        ListNode *fast = head, *slow = head;

        while(fast->next && fast->next->next){
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode *split = slow->next;
        slow->next = NULL;

        //反转后半部分
        ListNode *reverse = NULL;
        while(split){
            ListNode *temp = split->next;
            split->next = reverse;
            reverse = split;
            split = temp;
        }

        //将反转后的后半部分插入到前半部分
        ListNode *p = head;
        while(reverse){
            ListNode *temp = reverse->next;

            reverse->next = p->next;
            p->next = reverse;

            p = p->next->next;
            reverse = temp;
        }
    }
};