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 may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

---

本题要求把单链表重新排序，规则是第一个节点接最后一个节点，第二个节点接倒数第二个节点，以此类推。要求in-place，不能借助额外的空间。 这个题我一开始想到的是递归解法，就是首先把L0和Ln接好，然后递归的在L1->…->L(n-1)重排序。但是这样的算法性能肯定很差，因为首先要找到尾节点就很麻烦，还要递归的找尾节点。

看了网上的题解，发现真是巧妙。把链表重排序之后的结果其实相当于先把链表从中点分成前后两段，然后把后半段链表逆序，最后合并两个链表，合并的时候交替从两个链表中取节点拼接起来。 举个例子，0->1->2->3->4，中点是2，分成两段之后就是0->1和2->3->4，然后把第二个链表逆序为4->3->2，最后交替拼接这两个链表，结果就是0->4->1->3->2。、 所以知道思路之后就好办了，找中点可以用快慢指针法，链表逆序用头插法，最后拼接也不是什么难事，不过整合起来代码稍微有点长。 完整代码如下：

class Solution {
public:
    void reorderList(ListNode* head)
    {
        if (head == NULL || head->next == NULL || head->next->next == NULL)
            return; // find mid node
        ListNode *slow = head, *fast = head, *pre = slow;
        while (slow->next != NULL && fast != NULL && fast->next != NULL) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = NULL;
        // reverse [mid,end]
        ListNode *par = new ListNode(0), *tail;
        while (slow) {
            tail = slow->next;
            slow->next = par->next;
            par->next = slow;
            slow = tail;
        }
        //merge 2 list
        par = par->next;
        ListNode *new_head = new ListNode(0), *h = new_head;
        while (head || par) {
            if (head == NULL) {
                h->next = par;
                par = par->next;
            }
            else {
                h->next = head;
                head = head->next;
                h = h->next;
                h->next = par;
                par = par->next;
            }
            h = h->next;
        }
        head = new_head->next;
    }
};

本代码提交AC，用时59MS。