leetcode23 Merge k Sorted Lists

思路：
分治。
实现：
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct ListNode
 5 {
 6     int val;
 7     ListNode *next;
 8     ListNode(int x) : val(x), next(NULL) {}
 9 };
10  
11 class Solution 
12 {
13 public:
14     ListNode* mergeKLists(vector<ListNode*>& lists)
15     {
16         int K = lists.size();
17         if (!K) return NULL;
18         return merge(lists, 0, K - 1);
19     }
20     ListNode* merge(vector<ListNode*>& lists, int l, int r)
21     {
22         if (l == r) return lists[l];
23         else
24         {
25             int m = l + r >> 1;
26             ListNode* x = merge(lists, l, m);
27             ListNode* y = merge(lists, m + 1, r);
28             return merge2Lists(x, y);
29         }
30     }
31     ListNode* merge2Lists(ListNode* a, ListNode* b)
32     {
33         ListNode* t = NULL;
34         ListNode* ans = NULL;
35         while (a && b)
36         {
37             if (a->val < b->val)
38             {
39                 if (!t) { t = new ListNode(a->val); ans = t; }
40                 else { t->next = new ListNode(a->val); t = t->next; }
41                 a = a->next;
42             }
43             else
44             {
45                 if (!t) { t = new ListNode(b->val); ans = t; }
46                 else { t->next = new ListNode(b->val); t = t->next; }
47                 b = b->next;
48             }
49         }
50         while (a)
51         {
52             if (!t) { t = new ListNode(a->val); ans = t; }
53             else { t->next = new ListNode(a->val); t = t->next; }
54             a = a->next;
55         }
56         while (b)
57         {
58             if (!t) { t = new ListNode(b->val); ans = t; }
59             else { t->next = new ListNode(b->val); t = t->next; }
60             b = b->next;
61         }
62         return ans;
63     }
64 };
65 
66 int main()
67 {
68     vector<ListNode*> lists(3, NULL);
69     lists[0] = new ListNode(1);
70     lists[0]->next = new ListNode(4);
71     lists[0]->next->next = new ListNode(5);
72     lists[1] = new ListNode(1);
73     lists[1]->next = new ListNode(3);
74     lists[1]->next->next = new ListNode(4);
75     lists[2] = new ListNode(2);
76     lists[2]->next = new ListNode(6);
77     ListNode* ans = Solution().mergeKLists(lists);
78     while (ans)
79     {
80         cout << ans->val << " ";
81         ans = ans->next;
82     }
83     cout << endl;
84     return 0;
85 }