https://leetcode.cn/problems/merge-k-sorted-lists/?envType=study-plan-v2&envId=top-100-liked顺序合并
合并两个有序链表作为子函数，创建一个空链表，然后对含有多个链表的数组进行遍历，不断合并空链表与当前链表得到新链表直到遍历完毕。
//c++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mtwo(ListNode* h1,ListNode* h2)
{
if((!h1)||(!h2)) return h1?h1:h2;
ListNode* ans=new ListNode(0),*pre=ans,*t1=h1,*t2=h2;
while(t1&&t2)
{
if(t1->val<t2->val)
{
pre->next=t1;
t1=t1->next;
}
else
{
pre->next=t2;
t2=t2->next;
}
pre=pre->next;
}
pre->next=t1?t1:t2;
return ans->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists)
{
ListNode* ans=nullptr;
for(int i=0;i<lists.size();i++) ans=mtwo(ans,lists[i]);
return ans;
}
};
#python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mtwo(self, a:ListNode,b:ListNode)->ListNode:
if not a or not b:
return a if a else b
h=t=ListNode()
aa,bb=a,b
while aa and bb:
if aa.val>bb.val:
t.next=bb
bb=bb.next
else:
t.next=aa
aa=aa.next
t=t.next
t.next=aa if aa else bb
return h.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
ans=None
for i in lists:
ans=self.mtwo(ans,i)
return ans
分治合并
合并两个有序链表作为子函数，对含有多个链表的数组进行不断的二分递归，直到只含一个链表在回溯到上一个递归进行合并两个有序链表的操作直到回溯到对整个链表数组的合并。
//c++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mtwo(ListNode* h1,ListNode* h2)
{
if((!h1)||(!h2)) return h1?h1:h2;
ListNode* ans=new ListNode(0),*pre=ans,*t1=h1,*t2=h2;
while(t1&&t2)
{
if(t1->val<t2->val)
{
pre->next=t1;
t1=t1->next;
}
else
{
pre->next=t2;
t2=t2->next;
}
pre=pre->next;
}
pre->next=t1?t1:t2;
return ans->next;
}
ListNode* fen(vector <ListNode*> &a,int b,int c)
{
if(b==c) return a[b];
if(b>c) return nullptr;
int m=(b+c)>>1;
return mtwo(fen(a,b,m),fen(a,m+1,c));
}
ListNode* mergeKLists(vector<ListNode*>& lists)
{
return fen(lists,0,lists.size()-1);
}
};
#python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mtwo(self, a:ListNode,b:ListNode)->ListNode:
if not a or not b:
return a if a else b
h=t=ListNode()
aa,bb=a,b
while aa and bb:
if aa.val>bb.val:
t.next=bb
bb=bb.next
else:
t.next=aa
aa=aa.next
t=t.next
t.next=aa if aa else bb
return h.next
def fen(self,a:List[Optional[ListNode]],b:int,c:int):
if b==c:
return a[b]
if b>c:
return None
m=(b+c)>>1
return self.mtwo(self.fen(a,b,m),self.fen(a,m+1,c))
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
return self.fen(lists,0,len(lists)-1)
优先队列合并
c++应用结构体创造最小堆的优先队列，python用库函数heapq。对多个链表的数组的多个链表的第一个元素进行堆的初始化，然后不断取堆顶，并将堆顶的下一个元素入堆，直到堆为空。
//c++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
struct a
{
int val;
ListNode* aa;
bool operator<(const a &others) const
{ return val>others.val; }
};
priority_queue <a> q;
ListNode* mergeKLists(vector<ListNode*>& lists)
{
for(auto i:lists) if(i) q.push({i->val,i});
ListNode ans,*pre=&ans;
while(!q.empty())
{
auto i=q.top();
q.pop();
pre->next=i.aa;
pre=pre->next;
if(i.aa->next) q.push({i.aa->next->val,i.aa->next});
}
return ans.next;
}
};
#python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
import heapq
q=[]
for i,j in enumerate(lists):
if j:
heapq.heappush(q,(j.val,i,j))
ans=pre=ListNode(0)
while q:
i,j,k=heapq.heappop(q)
pre.next=k
pre=pre.next
if k.next:
heapq.heappush(q,(k.next.val,j,k.next))
return ans.next