题目：
给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
解题分析：
当链表节点数在两个以内时，无需重排；达到的效果是将链表右边比较大的一半链表倒序逐个插入左边里。可以将思路整理为这么几部分：
1：找出链表中间节点，在合适的地方链表截断。
中间节点之后的节点都是需要向左边插入的。如果纠结这个奇偶问题，可以就示例用快慢指针走一下，就会发现，slow->next就是需要择出来插左边的头结点。为描述方便，这里称右边需要拎出来的链表为大数链表，左边为小数链表。毫无疑问，大数链表比小数链表短。
2：按照题意，重排后，大数链表是倒序插入左边的，所以找出大数链表后，需要对大数链表进行翻转。
3：如果大数链表还有需要处理的节点，则向小数链表内间隔地插入节点。
解法1：纯链表操作
class Solution {
private:
ListNode* findMidNode(ListNode* head) { //找中间节点
ListNode *fast = head, *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverseList(ListNode* head) { //翻转链表
ListNode *former = head, *latter = NULL;
while (head) {
head = head->next;
former->next = latter;
latter = former;
former = head;
}
return latter;
}
public:
void reorderList(ListNode* head) {
if (NULL == head || NULL == head->next
|| NULL == head->next->next) //两个节点以内
return;
ListNode *ptr = findMidNode(head); //找到链表中点
ListNode *bigHead = ptr->next; //断掉小数链表和大数链表
ptr->next = NULL;
bigHead = reverseList(bigHead); //翻转大数链表
ptr = head;
ListNode *former = head->next;
while (bigHead) { //向小数链表里插大数节点
ptr->next = bigHead;
bigHead = bigHead->next;
ptr->next->next = former;
ptr = ptr->next->next;
former = former->next;
}
}
};
如果想让指针的命名直接易懂，不封装函数真的很难做到，不然就为起个贴切的好名字声明一堆指针就太浪费空间了。
解法2：空间换时间
将所有节点放入数组里，利用数组的下标直接对节点进行访问。
解法3：找到中间链表后，用栈代替翻转
用栈的先进后出处理大数链表，自然可以先找到最大数的节点，这样就不用翻转大数链表了。
