reorder-list 重排链表

题目：

将给定的单链表L： L 0→L 1→…→L n-1→L n,

重新排序为： L 0→L n →L 1→L n-1→L 2→L n-2→…

要求使用原地算法，并且不改变节点的值

例如：

对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.

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

代码：

 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         if(head == NULL)
13             return;
14         //快慢指针找到中间节点
15         ListNode* slow = head;
16         ListNode* fast = head;
17         while(fast->next != NULL && fast->next->next != NULL){
18             slow = slow->next;
19             fast = fast->next->next;
20         }
21         ListNode* l1 = head;
22         ListNode* l2 = slow->next;
23         slow->next = NULL;
24         //反转后半段链表
25         ListNode* newhead = new ListNode(NULL);
26         ListNode* pre = newhead;
27         while( l2 != NULL){
28             ListNode* temp = l2->next;
29             l2->next = pre->next;
30             pre->next = l2;
31             l2 = temp;
32         }
33         l2 = pre->next;
34         //合并两个链表
35         while( l2 != NULL ){
36             ListNode* l1_next = l1->next;
37             ListNode* l2_next = l2->next;
38             l1->next = l2;
39             l2->next = l1_next;
40             l1 = l1_next;
41             l2 = l2_next;
42         }
43     }
44 };

我的笔记：

通过快慢指针找到链表中的中间结点，并将其进行反转，最后再将两个链表合并即可。

注意：分割链表之后一定是 l1 较长。