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% 的用户

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • c++ 如何合并两个有序链表

    1.题目要求 这是一道求职面试时经常要求手写或者机试的经典题目. 已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序.结果链表要包含head1和head2的所有节点,即使节点值相同. 注意:不能开辟新空间来存储合并后的链表.如果第一次做该题,很容易会想到使用新链表来存储合并后的有序链表.虽然可以如此实现,但是不符合常规解法和面试官的要求. 2.非递归实现 算法过程:  输入:两个有序的单链表head1与head2:  输出:合并后的有序单链表mergeHead:  算法描

  • 带你了解如何用C++合并两个有序链表

    目录 将两个升序链表合并为一个新的 升序 链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 思路 代码 链表Listnode详细介绍 总结 将两个升序链表合并为一个新的 升序 链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出:[] 示例 3: 输入:l1 = [], l2 = [0] 输出:[0] 思路 可以简

  • C++实现合并两个排序的链表

    本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下 问题描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; 方法一 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN

  • C++归并法+快速排序实现链表排序的方法

    本文主要介绍了C++归并法+快速排序实现链表排序的方法,分享给大家,具体如下: 我们可以试用归并排序解决: 对链表归并排序的过程如下. 找到链表的中点,以中点为分界,将链表拆分成两个子链表.寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点. 对两个子链表分别排序. 将两个排序后的子链表合并,得到完整的排序后的链表 上述过程可以通过递归实现.递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链

  • c++如何实现归并两个有序链表

    目录 归并两个有序链表 1.题目描述 2.设计思路 将两个有序链表合并为一个新的有序链表并返回 示例 在力扣上的提交结果 归并两个有序链表 1.题目描述 利用基础题里构建的单链表类创建两个有序的整数链表对象,实现将两个有序链表归并成一个新的有序链表并输出该新有序链表的结果.(可以调用已定义的链表类的方法来实现,并注意如何将两个有序的线性表进行归并的算法) 2.设计思路 首先通过InputRear()函数构造两个链表,通过不断修改last指针的指向. last->link = newNode; l

  • C++实现打印两个有序链表公共部分的方法

    本文实例讲述了C++实现打印两个有序链表公共部分的方法.分享给大家供大家参考,具体如下: 题目: 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分. 解题思路及代码: 1.head1的值小于head2,则head1往下移动 2.head1的值小于head2,则head2往下移动 3.相等则打印任何一个链表节点的值,head1和head2都往下移动. 4.当head1或head2移动到NULL,终止. 算法C++代码: typedef struct Node { int da

  • Python实现合并两个有序链表的方法示例

    本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj

  • JS实现的合并两个有序链表算法示例

    本文实例讲述了JS实现的合并两个有序链表算法.分享给大家供大家参考,具体如下: 将两个有序链表合并为一个新的有序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 可以直接运行的方案: <script> function Node(element) { this.element = element;//当前节点的元素 this.next = n

  • Java合并两个及以上有序链表的示例详解

    目录 题目一:合并两个有序链表 题目一思路 题目一完整代码 题目二:合并多个有序链表 题目二关键思路 题目二完整代码 题目一:合并两个有序链表 题目链接 题目一思路 设置两个指针,一个指针(t1)指向l1链表头,另外一个指针(t2)指向l2链表头. 首先判断l1和l2的第一个元素,谁小,谁就是最后要返回的链表的头节点,如果l1和l2的第一个元素相等,随便取哪个都可以. 这样,我们就设置好了要返回链表的头节点,假设头节点是head, 依次移动t1和t2指针,谁小,谁就接入进来.依次操作,直到两个链

  • C/C++合并两个升序链表的方式

    目录 合并两个升序链表 算法的思想 代码实现+注释 合并K个升序链表(递归方法) 归并的思想 先来看合并两个有序链表的代码 我们再来看合并K个链表的递归方法 合并两个升序链表 算法的思想 1.需要合并的两个链表La,Lb,合并之后的链表Lc(用La的头节点). 2.定义两个辅助指针Pa,Pb分别是链表La,Lb的复制指针. 3.从首元节点开始比较,当两个链表都没有到达链表尾部的时候,依次取其中较小的数据进行链接到Lc的最后 4.如果两个元素的值相同,取La链的,把Lb链表的元素删除(确保新链表没

  • python实现合并两个有序列表的示例代码

    题目描述 将两个升序链表合并为一个新的升序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. LeetCode原题地址:https://leetcode-cn.com/problems/merge-two-sorted-lists/ 测试用例 示例1 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例2 输入:l1 = [], l2 = [] 输出:[] 示例3 输入:l1 = [], l2 = [0] 输出:[0] 代码详解 因为Lee

  • C++实现LeetCode(23.合并k个有序链表)

    [LeetCode] 23. Merge k Sorted Lists 合并k个有序链表 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 这

随机推荐