143. Reorder List，143reorderlist

143. Reorder List，143reorderlist

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

 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         }
15         
16         
17         
18         ListNode* fast = head;
19         ListNode* slow = head;
20         
21         while(fast->next != NULL && fast->next->next != NULL){
22             fast = fast->next->next;
23             slow = slow->next;
24         }
25         fast = slow->next;
26         slow->next = NULL;
27         
28         fast = ReverseList(fast);
29         
30         slow = head;
31         
32         while(slow){
33             if(fast != NULL){
34                 ListNode* n = slow->next;
35                 slow->next = fast;
36                 ListNode* nn = fast->next;
37                 fast->next = n;
38                 fast = nn;
39                 slow = n;
40             }else{
41                 break;
42             }
43         }
44     }
45     
46     
47     ListNode* ReverseList(ListNode* pHead){
48         ListNode* pReversedHead = NULL;
49         ListNode* pNode = pHead;
50         ListNode* pPrev = NULL;
51         
52         while(pNode != NULL){
53             ListNode* pNext = pNode->next;
54             
55             if(pNext == NULL){
56                 pReversedHead = pNode;
57             }
58             
59             pNode->next = pPrev;
60             pPrev = pNode;
61             pNode = pNext;
62         }
63         return pReversedHead;
64     }
65 };