c++如何实现归并两个有序链表

第c++如何实现归并两个有序链表目录归并两个有序链表1、题目描述2、设计思路将两个有序链表合并为一个新的有序链表并返回示例在力扣上的提交结果

归并两个有序链表

1、题目描述

利用基础题里构建的单链表类创建两个有序的整数链表对象，实现将两个有序链表归并成一个新的有序链表并输出该新有序链表的结果。（可以调用已定义的链表类的方法来实现，并注意如何将两个有序的线性表进行归并的算法）

2、设计思路

首先通过InputRear()函数构造两个链表，通过不断修改last指针的指向。

last-link=newNode;

last=newNode;

只要用户没有输入标志结束的数据0，便一直将链表扩展下去。

最终令last-link=NULL;

链表的合并，整体思路与顺序表的合并相似，通过比较两个链表元素的大小，将小的元素赋值给新的链表，指针不断改变指向以循环整个链表

r-link=p;

r=p;

p=p-link;

或者是

r-link=q;

r=q;

q=q-link;

与线性表不同的是，链表中判断一个链表是否取遍可用p是否等于NULL来确定，当一个链表取遍后，将另一个链表剩下的结点连接到新链表即可。

头文件代码如下：

#includeiostream

usingnamespacestd;

//#include"LinearList.h"

templateclassT

//结点结构定义

structLinkNode{

Tdata;

//结点数据

LinkNodeT*link;

//结点链接指针

LinkNode(LinkNodeT*ptr=NULL){link=ptr;}

//构造函数

LinkNode(constTitem,LinkNodeT*ptr=NULL){data=item;link=ptr;}

templateclassT

classList{

protected:

structLinkNodeT*first;

public:

List(){first=newLinkNodeT}

//构造函数

List(constTx){first=newLinkNodeT}

//构造函数

List(ListTL);

//复制构造函数

~List(){makeEmpty();}

//析构函数

voidmakeEmpty();

//将链表置空

intLength()const;

//计算链表的长度

LinkNodeT*getHead()const{returnfirst;}

LinkNodeT*Search(Tx);

//搜素数据为x的节点

LinkNodeT*Locate(inti)const;

//搜索第i个元素的地址

boolgetData(inti,Tx)const;

//取出第i个节点的数据

voidsetData(inti,Tx);

//用x修改第i个元素的值

boolInsert(inti,Tx);

//在第i个节点后插入新节点

boolRemove(inti,Tx);

//删除第i个节点数据返回到x中

boolIsEmpty()const

//判断表是否为NULL

{

returnfirst-link==NULLtrue:false;

}

boolIsFull()const{returnfalse;}

//判断表满

voidInputFront(T

endFlag);

//倒序创建单链表

voidInputRear(TendFlag);

//正序创建单链表

voidOutput();

//输出

};

.cpp文件如下：

#include"LinkList.h"

#includeiostream

usingnamespacestd;

templateclassT

ListT::List(ListTL){

//复制构造函数

Tvalue;

LinkNodeT*srcptr=L.getHead();

LinkNodeT*destptr=first=newLinkNodeT

while(srcptr-link!=NULL){

//逐一赋值

value=srcptr-link-data;

destptr-link=newLinkNodeT(value);

destptr=destptr-link;

//左值游动指针移动到下一个

srcptr=srcptr-link;

//右值游动指针移动到下一个

}

destptr-link=NULL;

templateclassT

voidListT::makeEmpty(){

LinkNodeT

while(first-link!=NULL){

q=first-link;

first-link=q-link;

deleteq;

}

templateclassT

intListT::Length()const{

//计算带附加头节点的单链表的长度

LinkNodeT*p=first-link;

intcount=0;

while(p!=NULL){

count++;

p=p-link;

}

returncount;

templateclassT

LinkNodeT*ListT::Search(Tx){

//在表中搜索含数据x的节点，搜索成功时返回该节点的地址，否则返回NULL

LinkNodeT*current=first-link;

while(current!=NULL){

if(current-data==x)break;

elsecurrent=current-link;

}

returncurrent;

templateclassT

LinkNodeT*ListT::Locate(inti)const{

//定位函数返回表中第i个节点的地址如果i0或者i超过链表长度则返回NULL

if(i0)returnNULL;

LinkNodeT*current=first;

intm=0;

while(current!=NULLmi){

current=current-link;

m++;

}

returncurrent;

templateclassT

boolListT::getData(inti,Tx)const{

//取出链表中第i个节点的data

if(i=0)returnNULL;

//数据非法返回false

LinkNodeT*current=Locate(i);

//借助定位函数直接定位到相应的节点

if(current==NULL)returnfalse;

//i超过单链表的长度返回false

else{

x=current-data;

returntrue;

}

templateclassT

voidListT::setData(inti,Tx){

//设置链表的第i个元素为x

if(i=0)return;

LinkNodeT*current=Locate(i);

if(current==NULL)return;

elsecurrent-data=x;

templateclassT

boolListT::Insert(inti,Tx){

//在i个节点之后插入新节点

LinkNodeT*current=Locate(i);

if(NULL==current)returnfalse;

LinkNodeT*newNode=newLinkNodeT

if(NULL==newNode)

cout"存储分配错误"endl;

newNode-link=current-link;

current-link=newNode;

returntrue;

templateclassT

boolListT::Remove(inti,Tx){

//将链表中第i个节点删除删除成功返回true并将删除的data存储在x中

LinkNodeT*current=Locate(i-1);

//定位到指向i节点的节点

if(NULL==current||NULL==current-link)returnfalse;

//不存在待删除的节点

LinkNodeT*del=current-link;

//标记待删除的节点

current-link=del-link;

//重新拉链

x=del-data;

//记录下删除节点的data

deletedel;

//释放删除节点

returntrue;

templateclassT

voidListT::Output(){

//单链表的输出函数：将单链表中所有节点的data按逻辑顺序输出到屏幕上

LinkNodeT*current=first-link;

//创建遍历指针

while(current!=NULL){

coutcurrent-data'';

current=current-link;

}

coutendl;

templateclassT

voidListT::InputRear(TendFlag){

//函数功能：顺序建立单链表

//函数参数：输入结束标志的数据

LinkNodeT*newNode,*last;

//需要一个指针时刻标记结尾

Tval;

makeEmpty();

cinval;

last=first;

//首先令last指针指向头节点

while(val!=endFlag){

newNode=newLinkNodeT(val);

if(newNode==NULL)

cout"内存分配错误"endl;

last-link=newNode;

last=newNode;

cinval;

}

last-link=NULL;

intmain()

Listint

Listint

Listint

LinkNodeint*p,*q,*r;

cout"请输入第一个链表(结束符为0)：";

x.InputRear(0);//以0作为结束符正序创建链表

cout"请输入第二个链表(结束符为0)：";

y.InputRear(0);

p=x.getHead();

q=y.getHead();

r=z.getHead();

//新链表

q=q-link;

p=p-link;

cout"归并前的链表一："endl;

x.Output();

cout"归并前的链表二："endl;

y.Output();

while(pq)

{

if(p-data=q-data)

{

r-link=p;

r=p;

p=p-link;

continue;

}

if(p-dataq-data)

{

r-link=q;

r=q;

q=q-link;

continue;

}

}

if(p)

//归并后对元素个数多的链表的单独处理

{

while(p)

{

r-link=p;

r=p;

p=p-link;

}

}

if(q)

{

while(q)

{

r-link=q;

r=q;

q=q-link;

}

}

cout"归并后的链表为："endl;

z.Output();

}

将两个有序链表合并为一个新的有序链表并返回

新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：1-2-4,1-3-4

输出：1-1-2-3-4-4

/**

*Definitionforsingly-linkedlist.

*structListNode{

*

intval;

*

ListNode*next;

*

ListNode(intx):val(x),next(NULL){}

*};

classSolution{

public:

ListNode*mergeTwoLists(ListNode*l1,ListNode*l2){

ListNode*p=newListNode(0);

ListNode*temp=p;

while(l1||l2){

if(l1==NULL){