23. Merge k Sorted Lists

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 while(sz>1){ 16 int k=(sz+1)>>1; 17 int lim=sz>>1; 18 for(int i=0;i<lim;i++) 19 lists[i]=merge(lists[i], lists[i+k]); 20 sz=k; 21 } 22 return lists[0]; 23 } 24 25 ListNode* merge(ListNode* p1, ListNode* p2){ 26 ListNode* p = new ListNode(0); 27 ListNode* cur=p; 28 while(p1!=NULL&&p2!=NULL){ 29 if(p1->val<p2->val){ 30 p->next=p1; 31 p1=p1->next; 32 p=p->next; 33 } 34 else{ 35 p->next=p2; 36 p2=p2->next; 37 p=p->next; 38 } 39 } 40 p->next = p1==NULL? p2:p1; 41 return cur->next; 42 } 43 };

其实有点像归并排序，两两一组进行排序，完事儿再对结果两两一组排序，直到排序完成。这个方法巧妙利用了下标，很强势。

排序的时候不是用的相邻两个链表，而是用的距离为k的两个链表目前已知的最快方法，20ms

 

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 int right=sz-1; 16 if(sz%2==1){ 17 lists.push_back(NULL); 18 right=sz; 19 } 20 while(right>0){ 21 if((right+1)%2==1){ 22 lists[right+1]=NULL; 23 ++right; 24 } 25 int count=0; 26 27 for(int i=0;i<right;i+=2){ 28 lists[count]=merge(lists[i], lists[i+1]); 29 ++count; 30 } 31 right=count-1; 32 } 33 return lists[0]; 34 } 35 36 ListNode* merge(ListNode* p1, ListNode* p2){ 37 ListNode* p = new ListNode(0); 38 ListNode* cur=p; 39 while(p1!=NULL&&p2!=NULL){ 40 if(p1->val<p2->val){ 41 p->next=p1; 42 p1=p1->next; 43 p=p->next; 44 } 45 else{ 46 p->next=p2; 47 p2=p2->next; 48 p=p->next; 49 } 50 } 51 p->next = p1==NULL? p2:p1; 52 return cur->next; 53 } 54 };

这个方法也还行，先对待排容器进行补充，保证待排容器的元素数量为偶数个

然后对相邻两个链表排序，结果依次存在容器头部

最后lists[0]就是排序完成的序列

速度也还可以，24ms

转载于:https://www.cnblogs.com/zhuangbijingdeboke/p/11316555.html

相关资源：JAVA上百实例源码以及开源项目