探讨:将两个链表非降序合并为一个链表并依然有序的实现方法
发布时间:2023-06-23 01:41:38
标签:合并两个有序链表
已知两个链表list1和list,2,各自非降序排列,将它们合并成另外一个链表list3,并且依然有序,要求保留所有节点。
实现过程中,list1中的节点和list2中的节点都转移到了list3中,注意泛型的友元函数的用法。
程序如有不足之处,还望指正!!!
定义List类
#include "stdafx.h"
#include <iostream>
using namespace std;
template<class T>
struct Node
{
T data;
Node<T> * next;
};
template <class T>
class MyList
{
public:
//构造函数,初始化一个头结点,data为空,next指向第一个节点
MyList()
{
phead = new Node<T>;
phead->data = NULL;
phead->next = NULL;
}
//析构函数,将整个链表删除,这里采用的是正序撤销
~MyList()
{
Node<T>* p;
p = phead;
while (p)
{
Node<T>* q;
q = p;
p = p->next;
delete q;
}
}
//复制构造函数
MyList(MyList& mylist)
{
Node<T>* q = mylist.phead->next;
Node<T>* pb = new Node<T>;
this->phead = pb;
while (q != NULL)
{
Node<T>* p = new Node<T>;
p->data = q->data;
p->next = NULL;
pb->next = p;
pb = p;
q = q->next;
}
}
//插入一个元素的方法,在第i个元素插入一个元素e,
//返回值为NOTE<T>型指针,指向插入的那个元素
Node<T>* Insert(int i, T e)
{
//在链表的第i个位置,插入一个元素e
int j = 0;
Node<T>* p;
p = phead;
while (p && j < i - 1)
{
p = p->next;
++j;
}
if (!p || j > i -1)
{
return phead;
}
Node<T>* q;
q = new Node<T>;
q->data = e;
q->next = p->next;
p->next = q;
return q;
}
//输出list中的元素
void Show()
{
Node<T> *p = phead->next;
while (NULL != p)
{
cout << p->data << " ";
p = p->next;
}
}
template<class T> friend void MergeList(MyList<T> &list1, MyList<T> &list2, MyList<T> &list3);
private:
Node<T>* phead;};
<PRE class=cpp name="code">// </PRE><PRE class=cpp name="code">//将两个链表合并成一个链表,并且依然有序。方法保留了合并之前list1和list2的节点,
//合并之后list1和list2消失。将list1和list2合并为list3
template<class T>
void MergeList(MyList<T> &list1, MyList<T> &list2, MyList<T> &list3)
{
Node<T> *head1 = list1.phead, *head2 = list2.phead;
Node<T> *head3 = list3.phead, *temp = NULL;
if (head1->next == NULL)
{//如果list1为空,则list3头指针指向list2
head3 = head2;
list2.phead->next = NULL;//将list2消除,防止析构函数析构list2时找不到对象
}
else if (head2->next == NULL)
{//如果list1为空,则list3头指针指向list2
head3 = head1;
list1.phead->next = NULL;//将list1消除,防止析构函数析构list2时找不到对象
}
head1 = head1->next;
list1.phead->next = NULL;//将list1消除,防止析构函数析构list2时找不到对象
head2 = head2->next;
list2.phead->next = NULL;//将list2消除,防止析构函数析构list2时找不到对象
if (head1->data < head2->data)
{//如果list1的第一个元素小于list2的第一个元素
head3->next = head1;//将list1的第一个元素接到list3上
head1 = head1->next;
}
else
{
head3->next = head2;//将list2的第一个元素接到list3上
head2 = head2->next;
}
temp = head3->next;//指向list3当前最后一个节点
while (head1 != NULL && head2 != NULL)
{
if (head1->data < head2->data)
{
temp->next = head1;//将list1中的元素接到list3的后面
temp = head1;
head1 = head1->next;
}
else
{
temp->next = head2;//将list2中的元素接到list3的后面
temp = head2;
head2 = head2->next;
}
}
if (NULL == head1) //将list1或者list2中的剩余部分接到list3的后面
{
temp->next = head2;
}
else if (NULL == head2)
{
temp->next = head1;
}
}<PRE class=cpp name="code"> </PRE><PRE class=cpp name="code">//主函数</PRE><PRE class=cpp name="code">int _tmain(int argc, _TCHAR* argv[])
{
MyList<int> list1, list2, list3;
for (int i = 1; i <= 10; i ++)
{
list1.Insert(i, 3*i);
list2.Insert(i, 2*i);
}
MergeList(list1, list2, list3);
list3.Show();
return 0;
}</PRE><BR>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
</PRE>
0
投稿
猜你喜欢
- 最近“全网域(Web Scale)”一词被炒得火热,人们也正在通过扩展他们的应用程序架构来使他们的系统变得更加“全网域”。但是究竟什么是全网
- 您已经看到很多包含视频内容的应用程序,比如带有视频教程的食谱应用程序、电影应用程序和体育相关的应用程序。您是否想知道如何将视频内容添加到您的
- 首先打开 Visual Studio Installer 可以看到vs2022 只支持安装4.6及以上的版本,如图所示。那么该如何安装4.6
- 参考:How to catch an Exception from a threadIs there a way to make Runna
- 本文主要介绍我为桌面和 Web 设计的一个超级秘密 Flutter 项目使用了画布和可拖动节点界面。本教程将展示我如何使用堆栈来使用小部件完
- 什么是JMMJMM全称Java Memory Model, 中文翻译Java内存模型,一种符合内存模型规范的,屏蔽了各种硬件和操作系统的访问
- 好久没有做web了,JSON目前比较流行,闲得没事,所以动手试试将对象序列化为JSON字符(尽管DotNet Framework
- 前言回想一下,在学Java时接触的正则表达式,其实Kotlin中也是类似。只不过使用Kotlin 的语法来表达,更为简洁。正则(Regex)
- 最近在看《.NET游戏编程入门经典 C#篇》 第一章介绍了如何制作俄罗斯方块,自己试了试按照书上的步骤,可算是完成了。于是写下这篇文章留作纪
- 需求: 给定一个URL地址, 例如: http://www.cncounter.com/tools/shorturl.php, 解析对应的I
- 一、Monkey 是什么?Monkey 就是SDK中附带的一个工具。二、Monkey 测试的目的?:该工具用于进行压力测试。 然后开发人员结
- 对于大文件的处理,无论是用户端还是服务端,如果一次性进行读取发送、接收都是不可取,很容易导致内存问题。所以对于大文件上传,采用切块分段上传,
- 报错翻译: compileSdkVersion android-24”需要JDK 1.8或更高版本编译。报错现象如下图:原因:st
- 目录转场形式设定页面默认转场方式跳转时指定转场方式总结在 fluro 中,定义路由处理器 Handler 时可以指定该页面的默认转场形式,或
- 文章来源:互联网在使用struts多模块的,找到一些小技巧和经验,与大家分享一下。 关于多module的配置就不说了,只需要用不
- [LeetCode] 2. Add Two Numbers 两个数字相加You are given two non-empty&n
- 最近没事写了一个简易浏览器,在刚开始写的时候遇到一些问题,主要的问题就是如何在自己的webview中显示所有的网页数据,不过不指
- 本文实例为大家分享了Android实现支付宝支付密码输入界面的具体代码,供大家参考,具体内容如下效果图:主要代码:import java.u
- 为什么要使用路由在之前我们的代码中,页面跳转使用的代码如下所示:Navigator.of(context).push( Mate
- 目录样例代码在讲 Flutter 的盒子模型前,先看看HTML 中的盒子模型。如下图所示,一个页面元素包括了与父级容器的外边距(margin