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     void reorderList(ListNode *head) { 2         // IMPORTANT: Please reset any member data you declared, as 3         // the same Solution instance will be reused for each test case. 4         stack
     
       s; 5         vector
      
        v; 6         if(head == NULL) 7             return; 8         ListNode *tmp = head; 9         int n = 0;10         while(tmp){11             n++;12             s.push(tmp);13             v.push_back(tmp);14             tmp = tmp->next;15         }16         int i;17         ListNode *n1, *n2;18         for(i = 0; i < n/2; i++){19             n1 = v[i];20             n2 = s.top();21             s.pop();22             n2->next = n1->next;23             n1->next = n2;24         }25         v[n/2]->next = NULL;26     }