题目描述：给链表如L: L0→L1→…→Ln-1→Ln，将其重新排序为L0→Ln→L1→Ln-1→L2→Ln-2→…，要求空间复杂度为O(1)，且不修改结点的值。
分析：若没有要求，可以先遍历链表在数组中记录每个结点的值，然后修改链表即可。纯链表操作就要在指针上做处理了，先找到中间结点断开，将后半截链表转置后与前半段merge。时间复杂度O(n)，空间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 || !head -> next) return ;
ListNode *slow = head, *fast = head, *pre = 0;
//设快慢指针用于找到链表中间结点，slow指针每次走一步，fast走两步，fast到链表尾结点时slow就在中间结点
while (fast && fast -> next) //由于fast一次走两步，故既可能直接跳过尾结点，也可能最后正好到尾结点，即链表结点个数奇偶的问题
{
pre = slow;
slow = slow -> next;
fast = fast -> next -> next;
}
pre -> next = nullptr; //pre是前半段的最后一个结点
slow = reverse(slow); //将后半段转置
//merge两链表
ListNode * cur = head;
while (cur -> next)
{
ListNode *tmp = cur -> next;
cur -> next = slow;
slow = slow -> next;
cur -> next -> next = tmp;
cur = tmp;
}
cur -> next = slow;
}
//转置两链表不是用的头插法，而是直接设三个指针指向连续的三个结点，在从前向后遍历的过程中修改当前cur所指结点的指针，指向其原前结点。
ListNode* reverse(ListNode *head)
{
if (!head || !head -> next) return head;
ListNode *pre = head;
for (ListNode *cur = head -> next, *nx = cur -> next;
cur;
pre = cur, cur = nx, nx = nx ? nx -> next : nullptr)
cur -> next = pre;
head -> next = nullptr;
return pre;
}
};
