剑指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攻城獅 的文章

關鍵字: 链表 单调 算法