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

来源：jb51　　时间：2022/7/20 11:08:31　　对本文有异议

归并两个有序链表

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。