题目：Reorder List

首尾重新结合形成新的链表；

要求：不能改变链表的元素，空间复杂度O(1)

题目意思：

将链表L0→L1→…→Ln-1→Ln重排变成L0→Ln→L1→Ln-1→L2→Ln-2→…

思路：

首先将链表分为前后两半；L0→L1→...→L(n+1)/2和L(n+1)/2 + 1→…→Ln-1→Ln

然后将后半段的链表逆置；Ln→Ln-1→…→L(n+1)/2 + 1

最后依次遍历两个链表将第二个（后半段）链表对应位置链接到第一个（前半段）的对应为置后面，这样拼接成新的链表。

如何逆置链表？

1.新建新的链表头，指向空指针；

2.从头开始遍历链表，按照如下顺序执行：

　　保存当前的下一个位置的节点，

　　将当前的下一个位置改为新链表的头部，

　　更新新链表的头部，使其指向当前链表，

　　更新当前指向的节点，使其指向前面保存的下一个位置；

3.循环执行上面的操作，知道链表为空，然后返回新链表的头指针。

L0→L1→L2→L3→L4→L5→L6→L7

新链表的头部为root = nullptr; p = head;head:L0.

循环的一次操作如下：　　　　　　　　　　第一轮　　　　　　　　第二轮　　　　...

ListNode* q = p->next;//保存下一个节点;q：L1　　　　　　　　q：L2

p->next = root;//当前节点插入头部;　　　p->next：nullptr　　 p->next：L0

root = p;//更新头结点；　　　　　　　　　root：L0　　　　　　 root：L1

p = q;//遍历后续节点　　　　　　　　　　 p：L1　　　　　　　  p：L2

ListNode *LeetCode::reverseList(ListNode* head){    ListNode* root = nullptr;//逆置后的头结点    ListNode* p = head;    while (p){        ListNode* q = p->next;//保存下一个节点        p->next = root;//当前节点插入头部        root = p;//更新头结点        p = q;//遍历后续节点    }    return root;}void LeetCode::reorderList(ListNode* head){    if (!head || !head->next)return;//空链，或单节点    int count = 0;//记录链长    ListNode* p = head;    while (p){
   //计算链长        p = p->next;        ++count;    }    if(count % 2)count = (count + 1) / 2;//奇数时，链的后半段的位置    else count = count / 2;    p = head;    for (; count > 0; --count)    {
    //找到后半段链的位置        if (count == 1){
   //将前半段链尾置空            ListNode* pre = p;            p = p->next;            pre->next = nullptr;            break;        }        p = p->next;    }    ListNode* q = p;    q = reverseList(q);//逆置后半段链表    p = head;    while (q){
   //交替拼接前后半段链表        ListNode* r = p->next;        p->next = q;        q = q->next;        p->next->next = r;        p = r;    }}