LeetCode第23题之Merge k Sorted Lists

本文主要是介绍LeetCode第23题之Merge k Sorted Lists，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

楼主是参考：http://www.cnblogs.com/skysand/p/4300711.html，感觉这篇博客写得挺好的。

C++代码：

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;/*** Definition for singly-linked list. */struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};class Solution {
public:// 小顶堆,以第i个元素为根建立小顶堆//位置从1开始，取元素时记得-1// 自顶向下void minHeap(vector<ListNode *> &heap, int i){int l = i*2;int r = i*2+1;int least = i;//如果左孩子存在，且左孩子小于父节点if (l-1<heap.size() && heap[l-1]->val < heap[least-1]->val){least = l;}if (r-1 < heap.size() && heap[r-1]->val < heap[least-1]->val){least = r;}//如果父节点的值不是最小if (least != i){swap(heap[i-1], heap[least-1]);minHeap(heap, least);}}// 建立小顶堆// 自低向上void makeHeap(vector<ListNode *> &heap){int sz = heap.size();for (int i=sz/2;i>0;--i){minHeap(heap,i);}}//弹出堆顶的元素ListNode *popHeap(vector<ListNode *>& heap){int sz = heap.size();if (sz > 0){swap(heap[0], heap[sz-1]);}ListNode * p = heap.back();heap.pop_back();minHeap(heap,1);return p;}// 在小顶堆中插入一个元素// 自低向上void pushHeap(vector<ListNode *> &heap, ListNode *p){heap.push_back(p);int child = heap.size();int parent = child/2;while (parent && heap[child-1]->val < heap[parent-1]->val){swap(heap[child-1], heap[parent-1]);child = parent;parent /= 2;}}ListNode* mergeKLists(vector<ListNode*>& lists) {// 使用堆排序, // 1. 选出每个链表的头来插入小顶堆中，// 2. 再把堆顶接入合并链表中，// 3. 被选出的指针后移再加入小顶堆中,回到2// 4. 最后所有链表都为空时，返回合并链表的头指针int sz = lists.size();if (0 == sz) return NULL;vector<ListNode *> heap;// 1. 选出每个链表的头来插入小顶堆中，for (int i=0;i<sz;++i){if (lists[i]) heap.push_back(lists[i]);}makeHeap(heap);/*for (int i=0;i<heap.size();++i){cout<<heap[i]->val<<'\t';}cout<<endl;*/// 2. 再把堆顶接入合并链表中，ListNode head(-1);ListNode *p = &head;ListNode *tmp = NULL;while(!heap.empty()){tmp = popHeap(heap);p->next = tmp;p = p->next;// 3. 被选出的指针后移再加入小顶堆中,回到2if (tmp->next){pushHeap(heap, tmp->next);}}// 4. 最后所有链表都为空时，返回合并链表的头指针return head->next;}
};void print_list(vector<ListNode *> lists)
{for (int i=0;i<lists.size();++i){ListNode *p = lists[i];while(p){cout<<p->val<<'\t';p = p->next;}cout<<endl;}
}int main()
{Solution s;vector<ListNode *> lists;for (int i=0;i<4;++i){ListNode *head,*p;head = NULL;for (int j=5;j>i;--j){p = head;head = new ListNode(j);head->next = p;//      head = p;}lists.push_back(head);  }
//  print_list(lists);ListNode * res = s.mergeKLists(lists);while(res){cout<<res->val<<'\t';res = res->next;}cout<<endl;return 0;
}

**优化代码：

后来想到既然堆每次加入一个元素的时候都要调整堆顶，那么每次把要添加的元素换到堆顶再调整就不用写pushHeap的函数了，当要添加的元素为空时，相当于执行popHeap函数，因此可以简化代码：**

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;/*** Definition for singly-linked list. */struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};class Solution {
public:// 小顶堆,以第i个元素为根建立小顶堆//位置从1开始，取元素时记得-1// 自顶向下void minHeap(vector<ListNode *> &heap, int i){int l = i*2;int r = i*2+1;int least = i;//如果左孩子存在，且左孩子小于父节点if (l-1<heap.size() && heap[l-1]->val < heap[least-1]->val){least = l;}if (r-1 < heap.size() && heap[r-1]->val < heap[least-1]->val){least = r;}//如果父节点的值不是最小if (least != i){swap(heap[i-1], heap[least-1]);minHeap(heap, least);}}void makeHeap(vector<ListNode *> &heap){int sz = heap.size();for (int i=sz/2;i>0;--i){minHeap(heap,i);}}ListNode* mergeKLists(vector<ListNode*>& lists) {int sz = lists.size();if (0 == sz) return NULL;vector<ListNode *> heap;//将每条链表的首节点的指针加入到heap堆中for (int i=0;i<sz;++i){if (lists[i]) heap.push_back(lists[i]);}makeHeap(heap);/*for (int i=0;i<heap.size();++i){cout<<heap[i]->val<<'\t';}cout<<endl;*/ListNode head(-1);ListNode *p = &head;ListNode *tmp = NULL;while(!heap.empty()){tmp = heap[0];p->next = tmp;p = tmp;if (tmp->next){heap[0] = tmp->next;        }else{swap(heap[0],heap[heap.size()-1]);heap.pop_back();}minHeap(heap,1);}return head->next;}
};void print_list(vector<ListNode *> lists)
{for (int i=0;i<lists.size();++i){ListNode *p = lists[i];while(p){cout<<p->val<<'\t';p = p->next;}cout<<endl;}
}int main()
{Solution s;vector<ListNode *> lists;for (int i=0;i<4;++i){ListNode *head,*p;head = NULL;for (int j=5;j>i;--j){p = head;head = new ListNode(j);head->next = p;//      head = p;}lists.push_back(head);  }
//  print_list(lists);ListNode * res = s.mergeKLists(lists);while(res){cout<<res->val<<'\t';res = res->next;}cout<<endl;return 0;
}