LeetCode Reorder List

 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  
12     ListNode* reverse(ListNode* head) {
13         if (head == NULL) {
14             return NULL;
15         }
16         ListNode* pre = NULL;
17         ListNode* cur = head;
18         while (cur != NULL) {
19             ListNode* tmp = cur->next;
20             cur->next = pre;
21             pre = cur;
22             cur = tmp;
23         }
24         return pre;
25     }
26 
27 
28     void reorderList(ListNode *head) {
29         if (head == NULL || head->next == NULL) {
30             return;
31         }
32         int num = 0;
33         ListNode* cur = head;
34         while (cur != NULL) {
35             num++;
36             cur = cur->next;
37         }
38         // seperate list, find middle node as the head of the new list
39         int ridx = num / 2;
40         ListNode* rhead = NULL;
41         cur = head;
42         for (int i=0; true; i++) {
43             if (i == ridx - 1) {
44                 rhead = cur->next;
45                 cur->next = NULL;
46                 break;
47             }
48             cur = cur->next;
49         }
50  
51         rhead = reverse(rhead);
52         
53         cur = head;
54         head = head->next;
55     
56         cur->next = rhead;
57         cur = rhead;
58         rhead = rhead->next;
59             
60         while (head != NULL && rhead != NULL) {
61             cur->next = head;
62             cur = head;
63             head = head->next;
64                 
65             cur->next = rhead;
66             cur = rhead;
67             rhead = rhead->next;
68         }
69         cur->next = rhead; // there must be only one node left(odd case) or NULL(even case)
70     }
71 
72 };