leetcode(23. Merge k Sorted Lists)

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
将一个链表数组合成一个有序的链表，其中链表中的数组都是有序链表。
方法1：两两合并链表数组元素，直到最终数组中只剩下一个元素。
使用一个递归的函数合并两个链表，返回值是合并后的链表。

 1 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 2         if(l1 == NULL) {
 3             return l2;
 4         }
 5         if(l2 == NULL) {
 6             return l1;
 7         }
 8         
 9         if(l1->val <= l2->val) {
10             l1->next = mergeTwoLists(l1->next, l2);
11             return l1;
12         }else {
13             l2->next = mergeTwoLists(l1, l2->next);
14             return l2;
15         }
16     }
17     ListNode* mergeKLists(vector<ListNode*>& lists) {
18         if(lists.empty()){
19             return nullptr;
20         }
21         while(lists.size() > 1) {
22             lists.push_back(mergeTwoLists(lists[0], lists[1]));
23             lists.erase(lists.begin());
24             lists.erase(lists.begin());
25         }
26         return lists.front();
27     }

复杂度：递归合并两个链表MAX(n, m)复杂度，循环链表数组数组复杂度为l, 最终复杂度应该为l*MAX(m, n).

方法2：使用优先队列，关键在于对优先队列熟悉。

 1 ListNode* mergeKLists(vector<ListNode*>& lists) {
 2         priority_queue<pair<int,ListNode*> ,vector<pair<int,ListNode*> > ,greater<pair<int,ListNode*> > > p;
 3         int i;
 4         ListNode* head=NULL;
 5         ListNode* head1=NULL;
 6         for(i=0;i<lists.size();++i)
 7         {
 8             ListNode* temp=lists[i];
 9                 if(temp!=NULL)
10                 p.push(make_pair(temp->val,temp));
11 
12         }
13         if(p.empty())
14         {
15             return head1;
16         }
17         pair<int,ListNode*> temp=p.top();
18         head1=temp.second;
19         head=temp.second;
20         p.pop();
21         if(head1->next)
22         p.push({head1->next->val , head1->next}) ;
23         while(!p.empty())
24         {
25             temp=p.top();
26             p.pop();
27             if(temp.second->next)
28             p.push({temp.second->next->val , temp.second->next}) ; 
29             head->next=temp.second;
30             head=head->next;
31         }
32         head->next=NULL;
33         return head1;
34     }

秒客网

leetcode(23. Merge k Sorted Lists)

相关文章