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来确定,当一个链表取遍后,将另一个链表剩下的结点连接到新链表即可。

头文件代码如下:

#include<iostream> using namespace std; //#include"LinearList.h" template <class T>  //结点结构定义 struct LinkNode {     T data;                         //结点数据      LinkNode<T>* link;    //结点链接指针     LinkNode(LinkNode<T>* ptr = NULL) { link = ptr; }  //构造函数         LinkNode(const T& item, LinkNode<T>* ptr = NULL) { data = item; link = ptr; } }; template<class T> class List{ protected:     struct LinkNode<T>* first; public:     List() { first = new LinkNode<T>; }         //构造函数     List(const T& x) { first = new LinkNode<T>(x); }      //构造函数     List(List<T>& L);             //复制构造函数     ~List() { makeEmpty(); }            //析构函数     void makeEmpty();             //将链表置空     int Length() const;             //计算链表的长度     LinkNode<T>* getHead() const { return first; }     LinkNode<T>* Search(T x);           //搜素数据为x的节点     LinkNode<T>* Locate(int i)const;          //搜索第i个元素的地址     bool getData(int i, T& x) const;         //取出第i个节点的数据     void setData(int i, T& x);           //用x修改第i个元素的值     bool Insert(int i, T& x);           //在第i个节点后插入新节点     bool Remove(int i, T& x);           //删除第i个节点数据返回到x中     bool IsEmpty() const            //判断表是否为NULL     {         return first->link == NULL ? true : false;     }     bool IsFull() const { return false; }        //判断表满     void InputFront(T  endFlag);          //倒序创建单链表     void InputRear(T endFlag);           //正序创建单链表     void Output();              //输出 };

.cpp文件如下:

#include"LinkList.h" #include<iostream> using namespace std; template<class T> List<T>::List(List<T>& L){     //复制构造函数     T value;     LinkNode<T>* srcptr = L.getHead();     LinkNode<T>* destptr = first = new LinkNode<T>;     while (srcptr->link != NULL) {          //逐一赋值         value = srcptr->link->data;         destptr->link = new LinkNode<T>(value);         destptr = destptr->link;          //左值游动指针移动到下一个         srcptr = srcptr->link;           //右值游动指针移动到下一个     }     destptr->link = NULL; } template<class T> void List<T>::makeEmpty() {     LinkNode<T> *q;     while(first->link!=NULL){         q=first->link;         first->link=q->link;         delete q;     } } template<class T> int List<T>::Length() const {     //计算带附加头节点的单链表的长度     LinkNode<T>* p = first->link;     int count = 0;     while (p != NULL) {         count++;         p = p->link;     }     return count; } template<class T> LinkNode<T>* List<T>::Search(T x) {     //在表中搜索含数据x的节点,搜索成功时返回该节点的地址,否则返回NULL     LinkNode<T>* current = first->link;     while (current != NULL) {         if (current->data == x) break;         else current=current->link;     }     return current; } template<class T> LinkNode<T>* List<T>::Locate(int i)const{     //定位函数 返回表中第i个节点的地址 如果i < 0 或者i 超过链表长度则返回NULL     if (i < 0) return NULL;     LinkNode<T>* current = first;     int m = 0;     while (current != NULL && m < i) {         current = current->link;         m++;     }     return current; } template<class T> bool List<T>::getData(int i, T& x) const {     //取出链表中第i个节点的data     if (i <= 0) return NULL;             //数据非法返回false     LinkNode<T>* current = Locate(i);         //借助定位函数直接定位到相应的节点     if (current == NULL) return false;             //i超过单链表的长度返回false     else {         x = current->data;         return true;     } } template<class T> void List<T>::setData(int i, T& x) {     //设置链表的第i个元素为x     if (i <= 0) return;     LinkNode<T>* current = Locate(i);     if (current == NULL) return;     else current->data = x; } template<class T> bool List<T>::Insert(int i, T& x) {     //在i个节点之后插入新节点     LinkNode<T>* current = Locate(i);     if (NULL == current) return false;     LinkNode<T>* newNode = new LinkNode<T>(x);     if (NULL == newNode)          cout << "存储分配错误" << endl;     newNode->link = current->link;     current->link = newNode;     return true; } template<class T> bool List<T>::Remove(int i, T& x) {     //将链表中第i个节点删除 删除成功返回true并将删除的data存储在x中     LinkNode<T>* current = Locate(i - 1);        //定位到指向i节点的节点     if (NULL == current || NULL == current->link) return false;             //不存在待删除的节点     LinkNode<T>* del = current->link;         //标记待删除的节点     current->link = del->link;           //重新拉链     x = del->data;              //记录下删除节点的data     delete del;               //释放删除节点     return true; } template<class T> void List<T>::Output(){     //单链表的输出函数 :将单链表中所有节点的data按逻辑顺序输出到屏幕上     LinkNode<T>* current = first->link;        //创建遍历指针     while (current != NULL) {         cout<<current->data << ' ';         current=current->link;     }     cout<<endl; } template<class T> void List<T>::InputRear(T endFlag) {     //函数功能 : 顺序建立单链表     //函数参数 : 输入结束标志的数据     LinkNode<T>* newNode, *last;          //需要一个指针时刻标记结尾     T val;     makeEmpty();     cin >> val;     last = first;              //首先令last指针指向头节点     while (val != endFlag) {         newNode = new LinkNode<T>(val);         if (newNode== NULL)              cout << "内存分配错误" << endl;         last->link = newNode;         last = newNode;         cin >> val;     }     last->link = NULL; } int main() {     List<int> x;      List<int> y;      List<int> z;     LinkNode <int>*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(p&&q)     {         if(p->data <= q->data)         {             r->link=p;             r = p;             p = p->link;             continue;         }         if(p->data>q->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

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {         ListNode* p = new ListNode(0);         ListNode* temp = p;         while( l1 || l2 ){             if(l1==NULL){                 p->next = l2;                 break;             }else if(l2==NULL){                 p->next = l1;                 break;             }else{                 if ( l1->val < l2->val ){                     p->next = l1;                     l1 = l1->next;                 }else{                     p->next = l2;                     l2 = l2->next;                 }                 p=p->next;             }         }         return temp->next;     } };

因为经过while循环后,指针p的位置已经发生改变,所以需要一个辅助指针temp保存其初始位置。

因为在定义指针p的时候给它赋值了一个自定义的ListNode节点地址(相当于一个附加头指针),所以最后函数返回的应该是该结点的下一个结点,即temp->next。

在力扣上的提交结果

执行用时 : 16 ms, 在Merge Two Sorted Lists的C++提交中击败了95.72% 的用户

内存消耗 : 8.9 MB, 在Merge Two Sorted Lists的C++提交中击败了84.45% 的用户

以上为个人经验,希望能给大家一个参考,也希望大家多多支持易知道(ezd.cc)。

推荐阅读

    关于数据结构:SQL中的链表

    关于数据结构:SQL中的链表,关于数据结构:SQL中的链表,列表,索引,方法,链接,Linked List in SQL什么是将链接列表存储在mysql数据库中的最佳方

    Java实现顺序表、链表结构

    Java实现顺序表、链表结构,Java,实现,顺序,表,、,链表,结构,顺序,表,定义,,顺序表定义:用一段物理地址连续的存储单元依次存储数据元素的线

    1分钟交你判断单链表是否有环问题

    1分钟交你判断单链表是否有环问题,节点,指针,小呆是某某计算机专业的学生。linglingling,伴随这铃声,同学们都准时来上课了。老师:这节课是计

    链表的特点是什么

    链表的特点是用一组任意的存储单元存储线性表的数据元素。链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过

    静态链表和动态链表的区别是什么

    静态链表和动态链表的区别:使用静态链表存储数据,需要预先申请足够大的一整块内存空间;使用动态链表存储数据,不需要预先申请内存空间,而是在

    在单链表中设置头结点的作用是什么

    在单链表中设置头结点的作用是方便运算的实现。单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表

    链表和数组的区别是什么

    链表和数组的区别:链表是链式存储结构,数组是顺序存储结构;链表通过指针连接元素,而数组则是把所有元素按顺序进行存储;链表插入和删除元素不

    单链表的存储密度大于还是小于1

    单链表的存储密度小于1。原因:“存储密度=单链表数据项所占空间/结点所占空间”,而“ 结点所占空间=数据项所占空间+存放后继结点地址的链域

    链表不具备的特点是什么

    链表不具备的特点是“可随机访问任何一个元素”。具有的特点:1、可随机访问任何一个元素;2、插入、删除操作不需要引动元素;3、无须事先估

    详解C语言中双向循环链表的实现

    详解C语言中双向循环链表的实现目录实现细节辅助理解图具体实现代码1、对链表进行初始化2、任意位置前的插入3、任意位置的删除4、头插