探讨:将两个链表非降序合并为一个链表并依然有序的实现方法
发布时间: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>
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- 在Android TV上一般选中某个View, 都会有焦点突出放大的效果, 但是当在RecyclerView中(ListView或GridV
- 一、POI的定义JAVA中操作Excel的有两种比较主流的工具包: JXL 和 POI 。jxl 只能操作Excel 95, 97, 200
- 近期开发收音机有个需求,将频率值以图片的形式显示出来(如结尾效果图所示)。然而,一开始用TextView写出来的效果太丑了,提交上去肯定不合
- 下面是一些我找到Android的ADB有用的命令。可以手动或使用自动构建和测试过程。查看设备adb devices如果多个设备连接则使用 u
- DataGridView 列有三种排序模式。每一列的排序模式是通过该列的 SortMode 属性指定的,该属性可以设置为以下的 DataGr
- 什么是进程?电脑中时会有很多单独运行的程序,每个程序有一个独立的进程,而进程之间是相互独立存在的。比如下图中的QQ、酷狗播放器、电脑管家等等
- 在上一篇《Android仿微信滑动弹出编辑、删除菜单效果、增加下拉刷新功能》里,已经带着大家学习如何使用SwipeMenuListView这
- 我遇到一个重复性操作,为了能偷懒发现idea的功能还比较实用纵列选择:Alt+鼠标左键大小写转换:Ctrl+Shirt+u使用小技巧:像这样
- 想要php版的朋友可以到这里下载测试 https://www.jb51.net/codes/83179.htmlimport java.io
- 一、定义登录控制器目录结构代码:1、创建TUser类package com.demo.pojo;import lombok.AllArgsC
- java字段值为null,不返回该字段类上打注解@JsonSerialize(include = JsonSerialize.Inclusi
- @Resource和@Autowired是Spring Framework中两种常用的注入方式,它们的作用是在Spring容器中自动装配Be
- android第一次新建项目是,相关依赖包需要下载很久,至少半小时,因为网速问题,还会多次下载失败。解决办法如下:1、通过镜像将gradle
- 前言Java中容器对象主要用来存储其他对象,根据实现原理不同,主要有3类常用的容器对象:1、ArrayList 使用数组结构存储容器中的元素
- 有时候会不可避免使用动态表或者列进行业务处理。下面学习几种动态表/列的使用方式:【1】使用预编译即,默认值。<select id=&q
- Java使用OpenCV3.2实现视频读取与播放,供大家参考,具体内容如下OpenCV从3.x版本开始其JAVA语言的SDK支持视频文件读写
- 什么是AOPAOP是Aspect Oriented Programming的缩写,即『面向切面编程』。它和我们平时接触到的OOP都是编程的不
- 1.基本概念首先我们需要弄清楚几个概念:面向对象是什么、类是什么、对象又是什么?还是逐个来说1.1面向对象我们常说Java是面向对象的语言,
- 在使用STL容器(比如map、list、vector等)的时候,是用放一个对象还是放一个对象指针,即是用vector<int>还
- trim中prefix与suffix等标签用法1.prefix 前缀增加的内容2.suffix 后缀增加的内容3.prefixOverrid