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é)點(diǎn)上
			pa = pa->next; //指針后移
		}
		else if (pa->data > pb->data)
		{ //把小的數(shù)據(jù)(pb)鏈接到Lc表上
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
		else
		{ //如果兩個(gè)元素的值相同，取La鏈的，把Lb鏈表的元素刪
			pc->next = pa;
			pc = pa;
			pa = pa->next;
			LNode *p = pb->next; //保存pb下一個(gè)節(jié)點(diǎn)
			delete (pb);
			pb = p;
		}
	}
	pc->next = pa?pa:pb;
	delete(Lb);
}

合并K個(gè)升序鏈表（遞歸方法）

這個(gè)題的思路和歸并排序的思路一樣。

歸并的思想

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

先來看合并兩個(gè)有序鏈表的代碼

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

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

返回head節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，因?yàn)閔ead節(jié)點(diǎn)是new出來的，要記得delete釋放掉這個(gè)節(jié)點(diǎn)的內(nèi)存。

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

我們?cè)賮砜春喜個(gè)鏈表的遞歸方法

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

class Solution {
public:
?? ?// 傳入存放了K個(gè)鏈表首節(jié)點(diǎn)的數(shù)組lists
? ? ListNode* mergeKLists(vector<ListNode*>& lists) {
? ? ? ? if(lists.empty()){
? ? ? ? ? ? return nullptr;
? ? ? ? }
? ? ? ? return mergeAll(lists,0,lists.size()-1);
? ? }
?? ?// 遞歸地對(duì)鏈表進(jìn)行兩兩合并
? ? 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;
? ? }
?? ?// 合并兩個(gè)有序鏈表的函數(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;
? ? }
};

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

您可能感興趣的文章: