描述

将给定的单链表 L： L0→L1→…→Ln−1→Ln
重新排序为：L0→Ln→L1→Ln−1→L2→Ln−2→…
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。
数据范围：链表长度0≤n≤20000 ，链表中每个节点的值满足0≤val≤1000
要求：空间复杂度 O(n) 并在链表上进行操作而不新建链表，时间复杂度 O(n)
进阶：空间复杂度 O(1) ， 时间复杂度 O(n)
问题分析：需要重排链表，最简单粗暴的就是定义一个指针数组，存放每个节点的指针，
但是这样空间复杂度太高了。因为重排是有规律的，从头节点开始每两个中间都加了一个
节点，而这个节点是从后往前的。通过推理可以发现如果后半段逆转，然后让p从头，q从
逆转后的后半段起点开始，逐个往p中间加入q。就可以完美的解决问题。
那么问题就拆分为：1、逆转后半段链表；2、往前半段每两个之间插入后半段的节点。
1、通过快慢指针快速定位到中间节点，然后逆转。
2、再定义两个指针*ptmp，*qtmp，ptmp=p->next，qtmp=q->next。然后就容易操作了。
具体函数看下面的代码，需要注意的地方有注释。
复杂度分析：
时间复杂度：O(n)，寻找中间节点O(n/2)，反转链表O(n/2)，插入节点O(n/2).
空间复杂度：O(1)，只需要定义常数个变量。 
/**
 * 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==NULL||head->next==NULL) return;
        ListNode *p,*q,*ptmp,*qtmp;
        p=head;q=head;
        while(q->next!=NULL&&q->next->next!=NULL)
            p=p->next,q=q->next->next;
        ptmp=p->next;//记录p的下一个节点作为旋转的开始节点
        //当L节点个数为奇数时，是以p作为最后一个节点的，所以需要让这个节点下一个指向null
        //当L节点个数为偶数时，是以后半段最后一个为结尾的，而后半段末尾已经指向null。
        p->next=NULL;//不管节点个数是偶数还是奇数，这么做都没问题
        p=head;
        q=reverse(ptmp);//从p->next开始旋转链表
        while(q!=NULL) {
            ptmp=p->next,qtmp=q->next;//分别保存p，q的下一个节点
            p->next=q,q->next=ptmp;//让p，q指针重新指向，也就是插入q节点
            p=ptmp,q=qtmp;
        }
    }
    //反转链表
    ListNode* reverse(ListNode *N) {
        if(N==NULL||N->next==NULL) return N;
        ListNode *p=NULL;
        ListNode *q=NULL;
        while(N!=NULL) {
            q=N;
            N=N->next;
            q->next=p;
            p=q;
        }
        return p;
    }
};