LeetCode:Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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}.

分析：先用快慢指针找到链表的中点，然后翻转链表后半部分，再和前半部分组合。需要注意的是把链表分成两半时，前半段的尾节点要置为NULL，翻转链表时也要把尾节点置为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         // IMPORTANT: Please reset any member data you declared, as
13         // the same Solution instance will be reused for each test case.
14         if(head == NULL || head->next == NULL)return;
15         ListNode *fastp = head, *lowp = head, *tail = NULL;
16         while(fastp != NULL && fastp->next != NULL)
17         {//利用快慢指针找到链表的中点
18             tail = lowp;
19             fastp = fastp->next->next;
20             lowp = lowp->next;
21         }
22         tail->next = NULL; //此时tail 指向前半段的结尾
23         reverseList(lowp);//翻转链表后半段
24         fastp = head;
25         tail = NULL;
26         while(fastp != NULL)
27         {
28             ListNode *tmp = lowp->next;
29             lowp->next = fastp->next;
30             fastp->next = lowp;
31             tail = lowp;
32             fastp = lowp->next;
33             lowp = tmp;
34         }
35         if(lowp != NULL)
36             tail->next = lowp;
37 
38     }
39     void reverseList(ListNode* &head)
40     {//翻转链表
41         if(head == NULL || head->next == NULL)return;
42         ListNode *pre = head, *p = pre->next;
43         while(p != NULL)
44         {
45             ListNode *tmp = p->next;
46             p->next = pre;
47             pre = p;
48             p = tmp;
49         }
50         head->next = NULL;
51         head = pre;
52     }
53 };

扩展：如果不是链表是数组怎么样得到相同的序列，请参考博客 here 完美洗牌算法