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 class Solution {
 2 public:
 3     void reverseList(ListNode* &head)
 4     {
 5         ListNode* cur = head;
 6         ListNode* pre = NULL;
 7         while (cur) {
 8             ListNode* next = cur->next;
 9             cur->next = pre;
10             pre = cur;
11             cur = next;
12         }
13         head = pre;
14     }
15     
16     void contact_a_to_b(ListNode* &a, ListNode* &b)
17     {
18         ListNode* tmp = a->next;
19         a->next = b;
20         a = tmp;
21     }
22     
23     void reorderList(ListNode *head) {
24         if (!head || !head->next) {
25             return;
26         }
27         
28         ListNode* slow = head;
29         ListNode* fast = head;
30         while (fast) {
31             fast = fast->next;
32             if (fast) {
33                 fast = fast->next;
34                 slow = slow->next;
35             }
36         }
37         
38         ListNode* a = head;
39         ListNode* b = slow->next;
40         slow->next = NULL;
41         reverseList(b);
42         
43         while (a && b) {
44             if (b) {
45             contact_a_to_b(a,b);
46             }
47             contact_a_to_b(b,a);
48         }
49         
50     }
51 };