热门标签 | HotTags
当前位置:  开发笔记 > IOS > 正文

探讨:将两个链表非降序合并为一个链表并依然有序的实现方法

本篇文章是对将两个链表非降序合并为一个链表并依然有序的实现方法进行了详细的分析介绍,需要的朋友参考下
已知两个链表list1和list,2,各自非降序排列,将它们合并成另外一个链表list3,并且依然有序,要求保留所有节点。
实现过程中,list1中的节点和list2中的节点都转移到了list3中,注意泛型的友元函数的用法。
程序如有不足之处,还望指正!!!
定义List类
代码如下:

#include "stdafx.h"
#include

using namespace std;
template
struct Node
{
 T data;
 Node * next;
};
template
class MyList
{
public:
 //构造函数,初始化一个头结点,data为空,next指向第一个节点
 MyList()
 {
  phead = new Node;
  phead->data = NULL;
  phead->next = NULL;
 }
 //析构函数,将整个链表删除,这里采用的是正序撤销
 ~MyList()
 {
  Node* p;
  p = phead;
  while (p)
  {
   Node* q;
   q = p;
   p = p->next;
   delete q;
  }
 }
 //复制构造函数
 MyList(MyList& mylist)
 {
  Node* q = mylist.phead->next;
  Node* pb = new Node;
  this->phead = pb;
  while (q != NULL)
  {
   Node* p = new Node;
   p->data = q->data;
   p->next = NULL;
   pb->next = p;
   pb = p;
   q = q->next;
  }
 }
 //插入一个元素的方法,在第i个元素插入一个元素e,
 //返回值为NOTE型指针,指向插入的那个元素
 Node* Insert(int i, T e)
 {
  //在链表的第i个位置,插入一个元素e
  int j = 0;
  Node* p;
  p = phead;
  while (p && j   {
   p = p->next;
   ++j;
  }
  if (!p || j > i -1)
  {
   return phead;
  }
  Node* q;
  q = new Node;
  q->data = e;
  q->next = p->next;
  p->next = q;
  return q;
 }
 //输出list中的元素
 void Show()
 {
  Node *p = phead->next;
  while (NULL != p)
  {
   cout <data <<" ";
   p = p->next;
  }
 }
  template friend void MergeList(MyList &list1, MyList &list2, MyList &list3);
private:
 Node* phead;};  

代码如下:

// 
//将两个链表合并成一个链表,并且依然有序。方法保留了合并之前list1和list2的节点,
//合并之后list1和list2消失。将list1和list2合并为list3
template
void MergeList(MyList &list1, MyList &list2, MyList &list3)
{
 Node *head1 = list1.phead, *head2 = list2.phead;
 Node *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 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 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;
 }
}
 
//主函数
int _tmain(int argc, _TCHAR* argv[])
{
 MyList 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;
}













推荐阅读
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文基于刘洪波老师的《英文词根词缀精讲》,深入探讨了多个重要词根词缀的起源及其相关词汇,帮助读者更好地理解和记忆英语单词。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • 如何优化2060显卡设置以提升《Apex英雄》游戏体验
    《Apex英雄》作为一款热门的战术竞技游戏,吸引了大量玩家。本文将探讨如何通过优化GeForce RTX 2060显卡设置,确保在《Apex英雄》中获得最佳性能和流畅的游戏体验。 ... [详细]
  • 本章将深入探讨移动 UI 设计的核心原则,帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧,您将能够创建出既美观又实用的移动应用。 ... [详细]
  • 本文介绍如何通过SQL查询从JDE(JD Edwards)系统中提取所有字典数据,涵盖关键表的关联和字段选择。具体包括F0004和F0005系列表的数据提取方法。 ... [详细]
  • 如何高效创建和使用字体图标
    在Web和移动开发中,为什么选择字体图标?主要原因是其卓越的性能,可以显著减少HTTP请求并优化页面加载速度。本文详细介绍了从设计到应用的字体图标制作流程,并提供了专业建议。 ... [详细]
  • 本文详细介绍了如何通过命令行启动MySQL服务,包括打开命令提示符窗口、进入MySQL的bin目录、输入正确的连接命令以及注意事项。文中还提供了更多相关命令的资源链接。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文将详细介绍在Windows 7环境下,检查U盘启动盘是否制作成功的多种方法,包括通过BIOS设置和使用模拟启动工具。 ... [详细]
  • 本文介绍如何使用 NSTimer 实现倒计时功能,详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器,确保在指定时间间隔内执行特定任务。 ... [详细]
  • 本文介绍了在Windows环境下使用pydoc工具的方法,并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外,还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 网络运维工程师负责确保企业IT基础设施的稳定运行,保障业务连续性和数据安全。他们需要具备多种技能,包括搭建和维护网络环境、监控系统性能、处理突发事件等。本文将探讨网络运维工程师的职业前景及其平均薪酬水平。 ... [详细]
author-avatar
手机用户随便转转
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有