[Leetcode] Reorder list 重排链表

Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…

You must do this in-place without altering the nodes' values.

For example,
Given{1,2,3,4}, reorder it to{1,4,2,3}.

反转以后的链表是，从左往右是，node₀->node_n->node₁->noden_n-1->.....，首先想到是将链表L按照这个规律重新赋值一遍，但题中说不能改变结点的值；然后想到将链表反转然后重新连接起来，如1->2->3->4，

按虚线那样走，形成1->4->2->3->3->2->4->1，若是结点的值都不相同，则遇到相同时，就可以断开形成，若是有相同，可先统计结点的个数，然后判断终止条件。这样就需要新建一个链表。所以想到将链表一分为二，反转后半段，然后重新连接起来，依旧是1->2->3->4，

这样思路就出来了，分三步走，第一步，将链表一分为二，用到快慢指针；第二步，反转第二部分，反转链表是很重要的根基；第三步，将两链表接起来。参考了JustDoIt的博客。

使用快慢指针将链表分成两段，采用这种方式会导致在链表结点个数为奇数的情况下，后半段的个数比前半段多一个。前半段一preSlow维结束，后半段一slow开始。所以在第三步将两子链表连接起来的时候，要注意判断反转以后以newBeg开始的后半段是否已经结束，没有，则连接上剩余部分即可。

针对反转链表，要认真的理解，关键是反转以后，要在新的链表结尾加上next=NULL。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     void reorderList(ListNode *head) 
12     {
13         if(head==NULL||head->next==NULL)
14             return;
15         //分成两段
16         ListNode *preSlow=NULL;
17         ListNode *slow=head,*fast=head;
18         while(fast&&fast->next)
19         {
20             preSlow=slow;
21             slow=slow->next;
22             fast=fast->next->next;
23         }  
24         preSlow->next=NULL; //前半段
25 
26         //反转后半段
27         ListNode *newBeg=slow;
28         ListNode *last=newBeg->next;
29         while(last)
30         {
31             ListNode *temp=last->next;
32             last->next=newBeg;
33             newBeg=last;
34             last=temp;
35         }
36         slow->next=NULL;
37 
38         //合并
39         fast=head;
40         preSlow=NULL;
41         while(fast) //注：以前半段为条件
42         {
43             ListNode *tem=newBeg->next;
44             newBeg->next=fast->next;
45             fast->next=newBeg;
46             fast=newBeg->next;
47             preSlow=newBeg;
48             newBeg=tem;
49         }
50         if(newBeg !=NULL)   //因节点个数为奇数时，后段比前段多一个，所以最后要判断
51             preSlow->next=newBeg;
52     }
53 };