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.

 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct ListNode {
 5        int val;
 6        ListNode *next;
 7     //ListNode(int x) : val(x), next(NULL) {}
 8 };
 9 
10 class Solution {
11 public:
12     void reorderList(ListNode* head) {
13        ListNode* back = head;
14        ListNode* tailer;
15        int maxPosi=0;
16        while(back)
17        {
18            ++maxPosi;
19            tailer = back;
20            back = back->next;
21        }
22 
23        int mid = maxPosi/2;
24        ListNode* midlle = head;
25        while(mid-- != 0)
26        {
27            midlle = midlle->next;
28        }
29 
30        Reverse(midlle);
31 
32        ListNode* tmp;
33        bool flag = true;
34 
35        while(maxPosi-- >1)
36        {
37               if(flag)
38               {
39                      tmp = head->next;
40                      head->next = tailer;
41                      head = tmp;
42                      flag = false;
43               }
44               else
45               {
46                      tmp = tailer->next;
47                      tailer->next = head;
48                      tailer = tmp;
49                      flag = true;
50               }
51        }
52     }
53 
54     ListNode* Reverse(ListNode* head)
55     {
56         if (!head)
57         {
58             return NULL;
59         }
60         ListNode* rtn=NULL;
61         ListNode* prev = head;
62         ListNode* back = head;
63         while(back)
64         {
65             prev = back;
66             back = back->next;
67 
68             prev->next = rtn;
69             rtn = prev;
70         }
71 
72         return rtn;
73     }
74 };
75 
76 int main()
77 {
78     ListNode node[] = {
79         {1,node+1},
80         {2,node+2},
81         {3,node+3},
82         {4,node+4},
83         {5,node+5},
84         {6,node+6},
85         {7,NULL}
86         };
87     ListNode* pNode = node;
88     Solution s;
89     s.reorderList(node);
90     while(pNode)
91     {
92         cout << pNode->val << endl;
93         pNode = pNode->next;
94     }
95 }

从中间位置rever list，然后两端开始一次重新组在一起。