C/C++合并两个升序链表的方式

来源：jb51　　时间：2022/7/20 11:08:43　　对本文有异议

合并两个升序链表

算法的思想

1.需要合并的两个链表La,Lb，合并之后的链表Lc(用La的头节点)。

2.定义两个辅助指针Pa,Pb分别是链表La,Lb的复制指针。

3.从首元节点开始比较，当两个链表都没有到达链表尾部的时候，依次取其中较小的数据进行链接到Lc的最后

4.如果两个元素的值相同，取La链的，把Lb链表的元素删除(确保新链表没有重复的元素)

5.当一个链表结束的时候，把非空链表剩余的所有元素链接在Lc表的最后

6.释放Lb的头节点(Lb链表就被删除了)

代码实现＋注释

void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc)
{
	LinkList pa, pb, pc;
	pa = La->next;
	pb = Lb->next;
	Lc = pc = La;
	while (pa && pb)
	{
		if (pa->data < pb->data)
		{ //把小的数据(pa)链接到Lc表上
			pc->next = pa;
			pc = pa;	   //保证指向最后的节点上
			pa = pa->next; //指针后移
		}
		else if (pa->data > pb->data)
		{ //把小的数据(pb)链接到Lc表上
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
		else
		{ //如果两个元素的值相同，取La链的，把Lb链表的元素删
			pc->next = pa;
			pc = pa;
			pa = pa->next;
			LNode *p = pb->next; //保存pb下一个节点
			delete (pb);
			pb = p;
		}
	}
	pc->next = pa?pa:pb;
	delete(Lb);
}

合并K个升序链表（递归方法）

这个题的思路和归并排序的思路一样。

归并的思想

递归地，或迭代地，将两个已经有序的数组或链表合并成一个有序的大数组或大链表。

先来看合并两个有序链表的代码

传入两个链表的头结点，new一个head节点当作合并后的链表的头结点，当两个链表都没有走到链尾的时候，将两链表的节点有序放入合并后的链表中。

当某一个链表已经走到了链尾，此时把另一个链表剩下的部分接到合并后的链表尾部。

返回head节点的下一个节点，因为head节点是new出来的，要记得delete释放掉这个节点的内存。

ListNode* mergeTwo(ListNode* l1,ListNode*l2){
?? ??? ?// new一个节点当作合并后的链表的头结点
? ? ? ? ListNode* head=new ListNode(0);
? ? ? ? ListNode* temp=head;
? ? ? ? // 当两个链表都没有走到链尾的时候，将两链表的节点有序放入合并后的链表中
? ? ? ? while(l1 && l2){
? ? ? ? ? ? if(l1->val <= l2->val){
? ? ? ? ? ? ? ? temp->next=l1;
? ? ? ? ? ? ? ? temp=temp->next;
? ? ? ? ? ? ? ? l1=l1->next;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? temp->next=l2;
? ? ? ? ? ? ? ? temp=temp->next;
? ? ? ? ? ? ? ? l2=l2->next;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 当某一个链表已经走到了链尾，此时把另一个链表剩下的部分接到合并后的链表尾部。
? ? ? ? if(l1){
? ? ? ? ? ? temp->next=l1;
? ? ? ? }else{
? ? ? ? ? ? temp->next=l2;
? ? ? ? }
? ? ? ? temp=head->next;
? ? ? ? delete head;
? ? ? ? head=nullptr;
? ? ? ? return temp;
? ? }

我们再来看合并K个链表的递归方法

数组lists内存放了K个链表首节点，我们将数组先分成两部分，再将每部分又分为两部分，直到分成了一个链表首节点为一部分，递归程序就走到底了，然后开始调用合并两个有序链表的函数，将链表两两合并，此时递归程序不断地返回上一级，直到将所有链表合并成一个链表。

class Solution {
public:
?? ?// 传入存放了K个链表首节点的数组lists
? ? ListNode* mergeKLists(vector<ListNode*>& lists) {
? ? ? ? if(lists.empty()){
? ? ? ? ? ? return nullptr;
? ? ? ? }
? ? ? ? return mergeAll(lists,0,lists.size()-1);
? ? }
?? ?// 递归地对链表进行两两合并
? ? ListNode* mergeAll(vector<ListNode*>& lists,int begin,int end){
? ? ? ? ListNode* l1=nullptr;
? ? ? ? ListNode* l2=nullptr;
? ? ? ? ListNode* res=nullptr;
? ? ? ? if(begin<end){
? ? ? ? ? ? int mid=(begin+end)/2;
? ? ? ? ? ? l1=mergeAll(lists,begin,mid);
? ? ? ? ? ? l2=mergeAll(lists,mid+1,end);
? ? ? ? ? ? res=mergeTwo(l1,l2);
? ? ? ? }else{
? ? ? ? ? ? return lists[begin];
? ? ? ? }
? ? ? ? return res;
? ? }
?? ?// 合并两个有序链表的函数
? ? ListNode* mergeTwo(ListNode* l1,ListNode*l2){
? ? ? ? ListNode* head=new ListNode(0);
? ? ? ? ListNode* temp=head;
? ? ? ? while(l1 && l2){
? ? ? ? ? ? if(l1->val <= l2->val){
? ? ? ? ? ? ? ? temp->next=l1;
? ? ? ? ? ? ? ? temp=temp->next;
? ? ? ? ? ? ? ? l1=l1->next;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? temp->next=l2;
? ? ? ? ? ? ? ? temp=temp->next;
? ? ? ? ? ? ? ? l2=l2->next;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(l1){
? ? ? ? ? ? temp->next=l1;
? ? ? ? }else{
? ? ? ? ? ? temp->next=l2;
? ? ? ? }
? ? ? ? temp=head->next;
? ? ? ? delete head;
? ? ? ? head=nullptr;
? ? ? ? return temp;
? ? }
};