C/C++合并兩個升序鏈表的方式

更新時間：2022年07月20日 09:30:38 作者：小源同學(xué)r

這篇文章主要介紹了C/C++合并兩個升序鏈表的方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

合并兩個升序鏈表

算法的思想

1.需要合并的兩個鏈表La,Lb，合并之后的鏈表Lc(用La的頭節(jié)點)。

2.定義兩個輔助指針Pa,Pb分別是鏈表La,Lb的復(fù)制指針。

3.從首元節(jié)點開始比較，當(dāng)兩個鏈表都沒有到達鏈表尾部的時候，依次取其中較小的數(shù)據(jù)進行鏈接到Lc的最后

4.如果兩個元素的值相同，取La鏈的，把Lb鏈表的元素刪除(確保新鏈表沒有重復(fù)的元素)

5.當(dāng)一個鏈表結(jié)束的時候，把非空鏈表剩余的所有元素鏈接在Lc表的最后

6.釋放Lb的頭節(jié)點(Lb鏈表就被刪除了)

代碼實現(xiàn)＋注釋

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)
		{ //把小的數(shù)據(jù)(pa)鏈接到Lc表上
			pc->next = pa;
			pc = pa;	   //保證指向最后的節(jié)點上
			pa = pa->next; //指針后移
		}
		else if (pa->data > pb->data)
		{ //把小的數(shù)據(jù)(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下一個節(jié)點
			delete (pb);
			pb = p;
		}
	}
	pc->next = pa?pa:pb;
	delete(Lb);
}

合并K個升序鏈表（遞歸方法）

這個題的思路和歸并排序的思路一樣。

歸并的思想

遞歸地，或迭代地，將兩個已經(jīng)有序的數(shù)組或鏈表合并成一個有序的大數(shù)組或大鏈表。

先來看合并兩個有序鏈表的代碼

傳入兩個鏈表的頭結(jié)點，new一個head節(jié)點當(dāng)作合并后的鏈表的頭結(jié)點，當(dāng)兩個鏈表都沒有走到鏈尾的時候，將兩鏈表的節(jié)點有序放入合并后的鏈表中。

當(dāng)某一個鏈表已經(jīng)走到了鏈尾，此時把另一個鏈表剩下的部分接到合并后的鏈表尾部。

返回head節(jié)點的下一個節(jié)點，因為head節(jié)點是new出來的，要記得delete釋放掉這個節(jié)點的內(nèi)存。

ListNode* mergeTwo(ListNode* l1,ListNode*l2){
?? ??? ?// new一個節(jié)點當(dāng)作合并后的鏈表的頭結(jié)點
? ? ? ? ListNode* head=new ListNode(0);
? ? ? ? ListNode* temp=head;
? ? ? ? // 當(dāng)兩個鏈表都沒有走到鏈尾的時候，將兩鏈表的節(jié)點有序放入合并后的鏈表中
? ? ? ? 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;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 當(dāng)某一個鏈表已經(jīng)走到了鏈尾，此時把另一個鏈表剩下的部分接到合并后的鏈表尾部。
? ? ? ? if(l1){
? ? ? ? ? ? temp->next=l1;
? ? ? ? }else{
? ? ? ? ? ? temp->next=l2;
? ? ? ? }
? ? ? ? temp=head->next;
? ? ? ? delete head;
? ? ? ? head=nullptr;
? ? ? ? return temp;
? ? }

我們再來看合并K個鏈表的遞歸方法

數(shù)組lists內(nèi)存放了K個鏈表首節(jié)點，我們將數(shù)組先分成兩部分，再將每部分又分為兩部分，直到分成了一個鏈表首節(jié)點為一部分，遞歸程序就走到底了，然后開始調(diào)用合并兩個有序鏈表的函數(shù)，將鏈表兩兩合并，此時遞歸程序不斷地返回上一級，直到將所有鏈表合并成一個鏈表。

class Solution {
public:
?? ?// 傳入存放了K個鏈表首節(jié)點的數(shù)組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;
? ? }
?? ?// 合并兩個有序鏈表的函數(shù)
? ? 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;
? ? }
};

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: