题目
给定一个单链表 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.
思路
正常的想法是，找到第n个节点插入0和1中，再找第n-1个节点插入1和2中，但由于单链表无法从后向前遍历的限制，此方法时间复杂度很高，我们可以想办法构造从后向前遍历的可能。
想法1：通过数组将链表节点存储起来，通过数组就能实现正序和逆序遍历了，由于数组一般存储的是链表节点对象的引用，空间复杂度也不会太高。
想法2：将链表一分为二，分为前半段和后半段，将后半段以反转单链表的方式反转，这样就可以实现第n个节点向n-1个节点遍历，然后将后半段插入前半段，此方法优点在于空间复杂度低。
代码1
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if(head==null) return;
int len = 0;
ListNode p = head,next;
while(p!=null){
len++;
p=p.next;
}
ListNode[] list = new ListNode[len];
p = head;
int i=len-1;
while(p!=null){
list[i--] = p;
p=p.next;
}
p = head;
i=0;
while(i<len/2){
next = p.next;
p.next = list[i];
list[i].next = next;
i++;
p = next;
}
if(p.next!=null&&p.next.next==p){
p.next = null;
}
}
}
分析：采用原生数组反向存储链表节点，因此须先求出链表长度。（个人认为采用Java提供的List,Queue等集合类，虽然操作方便，不用提前求出链表长度，但由于其内部一般有扩容机制（如果底层实现基于数组）或是有又一层链表结构的封装（如果底层实现基于链表））。效率并不会比普通数组来的高。
优化：存放链表逆序元素的数组的长度可以不用链表的长度len，而是len/2，因为只有后半端需要逆序。
扩展：反转单链表亦可采用此方法来实现（如果不要求原地反转）
代码2（copy网友代码,采用C实现）
void reorderList(ListNode* head) {
if(head==NULL || head->next == NULL)
return;
//快慢指针分出两段
ListNode *slow = head,*fast = head;
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
//后端反转
ListNode *needReverser = slow->next;
slow->next = NULL;
needReverser = reverse(needReverser);
//插入前端缝隙
ListNode *cur = head;
while(cur && needReverser){
ListNode *curSecond = needReverser;
needReverser = needReverser->next;
ListNode *nextCur = cur->next;
curSecond->next = cur->next;
cur->next = curSecond;
cur = nextCur;
}
}
ListNode *reverse(ListNode *head){
ListNode *p1 = NULL;
ListNode *p2 = head;
ListNode *p3 = p2;
while(p2){
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
return p1;
}
