148. Sort List

A typical divide and conquer solution.

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:    ListNode* sortList(ListNode* head) {  
12:      if (head == NULL || head->next == NULL) return head;  
13:      ListNode *slow = head, *fast = head, *prev = NULL;  
14:      while (fast && fast->next) {  
15:        prev = slow;  
16:        slow = slow->next;  
17:        fast = fast->next->next;  
18:      }  
19:      prev->next = NULL;  
20:      ListNode *l1 = sortList(head);  
21:      ListNode *l2 = sortList(slow);  
22:      ListNode *dummy = new ListNode(-1);  
23:      ListNode *cur = dummy;  
24:      while (l1 && l2) {  
25:        if (l1->val < l2->val) {  
26:          cur->next = l1;  
27:          l1 = l1->next;  
28:        } else {  
29:          cur->next = l2;  
30:          l2 = l2->next;  
31:        }  
32:        cur = cur->next;  
33:      }  
34:      if (l1) cur->next = l1;  
35:      if (l2) cur->next = l2;  
36:      cur = dummy->next;  
37:      delete dummy;  
38:      return cur;  
39:    }  
40:  };