143. Reorder List

Three steps:
(1) cut into two lists (note the first list must be longer or equal to the second list).
(2) reverse the second list.
(3) merge the two lists.

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 == NULL || head->next == NULL) return;  
13:      int count = countList(head);  
14:      count = (count + 1) / 2;  
15:      ListNode *prev = NULL, *cur = head;  
16:      while (count) {  
17:        count--;  
18:        prev = cur;  
19:        cur = cur->next;  
20:      }  
21:      prev->next = NULL;  
22:      ListNode *l1 = head;  
23:      ListNode *l2 = reverseList(cur);  
24:      while (l2) {  
25:        ListNode *tmp = l2->next;  
26:        l2->next = l1->next;  
27:        l1->next = l2;  
28:        l1 = l2->next;  
29:        l2 = tmp;  
30:      }  
31:      return;  
32:    }  
33:    int countList(ListNode* head) {  
34:      int count = 0;  
35:      while (head) {  
36:        count++;  
37:        head = head->next;  
38:      }  
39:      return count;  
40:    }  
41:    ListNode *reverseList(ListNode *head) {  
42:      ListNode *dummy = new ListNode(-1);  
43:      ListNode *cur = head;  
44:      while (cur) {  
45:        ListNode *tmp = cur;  
46:        cur = cur->next;  
47:        tmp->next = dummy->next;  
48:        dummy->next = tmp;  
49:      }  
50:      head = dummy->next;  
51:      delete dummy;  
52:      return head;  
53:    }  
54:  };