题目：

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}.

代码：

/**
* 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) return;
ListNode dummy(-);
dummy.next = head;
ListNode *p1 = &dummy, *p2 = &dummy;
// get the mid Node
for (; p2 && p2->next; p1 = p1->next, p2 = p2->next->next);
// reverse the second half list
for ( ListNode *prev = p1, *curr = p1->next; curr && curr->next; ){
ListNode *tmp = curr->next;
curr->next = curr->next->next;
tmp->next = prev->next;
prev->next = tmp;
}
// cut the list from mid and merge two list
for ( p2 = p1->next, p1->next = NULL,p1 = head; p2; ){
ListNode *tmp = p1->next;
p1->next = p2;
p2 = p2->next;
p1->next->next = tmp;
p1 = tmp;
}
}
};

Tips：

改了两次，终于AC的效率进入5%了。

算法的思路：

Step1. 找到中间节点（p1指向中间节点之前的节点）

Step2. 把后半个List进行reverse操作

Step3. 讲两个Lists进行merge操作

尽量减少循环体中的无谓语句（例如条件判断语句、赋值语句、开新的中间变量），这样可以提升程序效率。

===========================================

第二次过这道题，考察三个内容

（1）双指针找链表中点

（2）翻转链表

（3）合并链表

合并链表的部分不太熟练，虽然自己也写出来了AC的代码，但是有些丑陋。复习了之前的代码，把这三部分都完善了一下。

/**
* 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) {
ListNode dummpy(-);
dummpy.next = head;
// find mid ListNode
ListNode* p1 = &dummpy;
ListNode* p2 = &dummpy;
while ( p2 && p2->next )
{
p1 = p1->next;
p2 = p2->next->next;
}
// reverse the second
ListNode* second = p1->next;
p1->next = NULL;
ListNode dummpy2(-);
dummpy2.next = second;
ListNode* curr = second;
while ( curr && curr->next )
{
ListNode* tmp = curr->next;
curr->next = tmp->next;
tmp->next = dummpy2.next;
dummpy2.next = tmp;
}
// merge two sub lists
p1 = dummpy.next;
p2 = dummpy2.next;
while ( p2 )
{
ListNode* tmp = p1->next;
p1->next = p2;
p2 = p2->next;
p1->next->next = tmp;
p1 = tmp;
}
}
};