LeetCode之“链表”：Merge Two Sorted Lists && Merge k Sorted Lists

　 1. Merge Two Sorted Lists

　　题目要求：

　 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

　　这道题目题意是要将两个有序的链表合并为一个有序链表。为了编程方便，在程序中引入dummy节点。具体程序如下：

 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
12         ListNode *dummy = new ListNode(0);
13         ListNode *head = nullptr, *start = dummy;
14         int flag = true;
15         while(l1 && l2)
16         {
17             if(l1->val < l2->val)
18             {
19                 start->next = l1;
20                 l1 = l1->next;
21             }
22             else 
23             {
24                 start->next = l2;
25                 l2 = l2->next;
26             }
27             start = start->next;
28         }
29         
30         if(!l1)
31             start->next = l2;
32         else if(!l2)
33             start->next = l1;
34         
35         head = dummy->next;
36         delete dummy;
37         dummy = nullptr;
38         
39         return head;
40     }
41 };

　 2. Merge k Sorted Lists

　题目链接

　　题目要求：

　　Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

　　这道题本来想用比较直观的方法，但超时了。具体程序如下：

 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* mergeKLists(vector<ListNode*>& lists) {
12         int sz = lists.size();
13         if(sz == 0)
14             return nullptr;
15         
16         ListNode *node = new ListNode(0);
17         ListNode *head = nullptr, *start = node;
18         while(true)
19         {
20             int count = 0;
21             int minVal = INT_MAX;
22             int minNode = -1;
23             for(int i = 0; i < sz; i++)
24             {
25                 if(lists[i] && lists[i]->val < minVal)
26                 {
27                     minNode = i;
28                     minVal = lists[i]->val;
29                 }
30                 else if(!lists[i])
31                     count++;
32             }
33             
34             if(count != sz)
35             {
36                 start->next = lists[minNode];
37                 lists[minNode] = lists[minNode]->next;
38             }
39             else
40             {
41                 head = node->next;
42                 delete node;
43                 node = nullptr;
44                 
45                 return head;
46             }
47             
48             start = start->next;
49         }
50     }
51 };

View Code

　　后来参考网上的做法，用Divide and Conquer方法会比较好，具体程序如下：

 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 *mergeTwoLists(ListNode* l1, ListNode* l2) {
12         ListNode *node = new ListNode(0);
13         ListNode *head = nullptr, *start = node;
14         int flag = true;
15         while(l1 && l2)
16         {
17             if(l1->val < l2->val)
18             {
19                 start->next = l1;
20                 l1 = l1->next;
21             }
22             else 
23             {
24                 start->next = l2;
25                 l2 = l2->next;
26             }
27             start = start->next;
28         }
29         
30         if(!l1)
31             start->next = l2;
32         else if(!l2)
33             start->next = l1;
34         
35         head = node->next;
36         delete node;
37         node = nullptr;
38         
39         return head;
40     }
41 
42     ListNode *mergeKLists(vector<ListNode*>& lists, int low, int high)
43     {
44         if(low < high)
45         {
46             int mid = (low + high) / 2;
47             return mergeTwoLists(mergeKLists(lists, low, mid), mergeKLists(lists, mid + 1, high));
48         }
49         return lists[low];
50     }
51     
52     ListNode* mergeKLists(vector<ListNode*>& lists) {
53         int sz = lists.size();
54         if(sz == 0)
55             return nullptr;
56         
57         return mergeKLists(lists, 0, sz - 1);
58     }
59 };

　　算法分析摘自同一博文：

　　我们来分析一下上述算法的时间复杂度。假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。根据主定理，可以算出算法的总复杂度是O(nklogk)。如果不了解主定理的朋友，可以参见主定理-维基百科。空间复杂度的话是递归栈的大小O(logk)。