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

 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 || !head->next || !head->next->next) return;
13         
14         //find the medium node
15         ListNode* slow = head;
16         ListNode* fast = head;
17         while(fast && fast->next){
18             fast = fast->next->next;
19             slow = slow->next;
20         }
21         ListNode* secondPre = slow;
22         ListNode* secondStart = slow->next;
23         secondPre->next = NULL; //break the list into two parts
24         
25         //reverse the second part
26         ListNode* secondMove = secondStart->next;
27         secondStart->next = NULL; //generalize the second list
28         while(secondMove){
29             ListNode* secondAfter = secondMove->next;
30             secondMove->next = secondStart;
31             secondStart = secondMove;
32             secondMove = secondAfter;
33         }
34         //now secondStart is the begining of the second list
35         
36         //combine two lists
37         ListNode* firstStart = head;
38         while(firstStart && secondStart){
39             ListNode* firstTemp = firstStart;
40             firstStart = firstStart->next;
41             ListNode* secondTemp = secondStart;
42             secondStart = secondStart->next;
43             firstTemp->next = secondTemp;
44             secondTemp->next = firstStart;
45             //firstStart->next = secondStart;
46         }
47     }
48 };