劍指offer------合併兩個排好序的鏈表（ 史上最全）

題目：

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成後的鏈表，當然我們需要合成後的鏈表滿足單調遞增規則。

例子

如：鏈表1：1->3->5->9；鏈表2：2->4->6；合併後為：1->2->3->4->5->6->9。

鏈接：

劍指Offer：17題

思路標籤：

數據結構：

鏈表

算法：

遞歸

解答：

1. C++

對問題進行分解。

每次以兩個鏈表頭節點中的小值作為合併鏈表的下一個節點。

每次合併的操作都是相同的，故使用遞歸，或者不用遞歸。

注意代碼的魯棒性，即輸入鏈表為空的情況。

A.遞歸版本

1. 沒有去重：

<code>/*
struct Listnode
{
\tint value;
\tstruct Listnode* next;
}
*/

Listnode* Merge(Listnode* pHead1,Listnode* pHead2)
{
\tif(pHead1==NULL)
\t\treturn pHead2;
\telse if
\t\treturn pHead1;
\t
\tListnode* pMerge=NULL;
\t
\tif(pHead1->value<phead2->value)
\t{
\t\tpMerge=pHead1;
\t\tpMerge->next=Merge(pHead1->next,pHead2);
\t}
\telse
\t{
\t\tpMerge = pHead2;
\t\tpMerge->next = Merge(pHead1,pHead2->next);
\t} 

\t
\treturn pMerge;
}/<phead2->/<code>

2.去重：

<code>Listnode* Merge(Listnode* pHead1,Listnode* pHead2)
{
\tif(pHead1==NULL)
\t\treturn pHead2;
\telse if
\t\treturn pHead1;
\t
\tListnode* pMerge=NULL;
\t
\tif(pHead1->value<phead2->value)
\t{
\t\tpMerge=pHead1;
\t\tpMerge->next=Merge(pHead1->next,pHead2);
\t}
\telse if(pHead1->value>pHead2->value)
\t{
\t\tpMerge=pHead1;
\t\tpMerge->next=Merge(pHead1->next,pHead2);
\t}
\telse
\t{
\t\tListnode* s = pHead2;
\t\tpMerge=pHead1;
\t\tpMerge->next = Merge(pHead1->next,pHead2->next);
\t\tfree(s);
\t}
\t
\treturn pMerge;
}/<phead2->/<code>

B.遞歸版本

<code>//鏈表儲存
#define NULL 0
typedef int ElemType;
typedef struct LNode
{
\tElemType data;
\tstruct LNode* next;
}LNode,*LinkList;
 

void mergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{
\tLc=La;
\tLinkList pa = La->next;
\tLinkList pb = Lb->next;
\tLinkList pc = Lc;
\t
\twhile(pa && pb)
\t{
\t\tif(pa->datadata)
\t\t{
\t\t\tpc->next = pa;
\t\t\tpc = pa;
\t\t\tpa = pa->next;
\t\t}
\t\telse
\t\t{
\t\t\tpc->next = pb;
\t\t\tpc = pb;
\t\t\tpb = pb->next;
\t\t}
\t}\t
\t\tpc->next = pa?pa:pb;
\t\t
\t\tfree(Lb);
}/<code>

閱讀更多 CPP攻城獅 的文章

關鍵字: 鏈表 單調 算法