143. 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 may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

重新排列链表

1->2->3->4->5 to 1->5->2->4->3.

C++：

 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 || head->next == NULL)
13             return ;
14         ListNode* p1 = head ;
15         ListNode* p2 = head ;
16         while(p2->next != NULL && p2->next->next != NULL){
17             p1 = p1->next ;
18             p2 = p2->next->next ;
19         }
20         
21         //1->2->3->4->5->6 to 1->2->3->6->5->4
22         ListNode* head2 = p1->next ;
23         p1->next = NULL ;
24         
25         p2 = head2->next ;
26         head2->next = NULL;
27         while(p2 != NULL){
28             p1 = p2->next ;
29             p2->next = head2 ;
30             head2 = p2 ;
31             p2 = p1 ;
32         }
33 
34         // 1->2->3->6->5->4 to 1->6->2->5->3->4
35         p1 = head ;
36         p2 = head2 ;
37         while(p1 != NULL){
38             ListNode* t = p1->next ;
39             p1->next = p2 ;
40             p1 = p2 ;
41             p2 = t ;
42         }
43     }
44 };