CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章探讨:将两个链表非降序合并为一个链表并依然有序的实现方法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

已知两个链表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;   }  }  &nbsp;template<class T> friend void MergeList(MyList<T> &list1, MyList<T> &list2, MyList<T> &list3); private: &nbsp;Node<T>* phead;};   。

  。

复制代码 代码如下

<PRE class=cpp name="code">//&nbsp;</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">&nbsp;</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; } 。

最后此篇关于探讨:将两个链表非降序合并为一个链表并依然有序的实现方法的文章就讲到这里了,如果你想了解更多关于探讨:将两个链表非降序合并为一个链表并依然有序的实现方法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。