题目
将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
算法思想
从首元结点开始进行比较,当两个链表La和Lb均未到达表尾结点时,依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等,只摘取La表中的元素,删除Lb表中的元素,这样确保合并后的表中无重复的元素。当一个表到达表尾结点为空时,将非空表的剩余元素直接链接在Lc表的最后。最后释放表Lb的头结点。
完整代码
#include <iostream>
#include <stdlib.h>
using namespace std;
//将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void ListRead(LinkList &L){
//读取链表,即给链表添加数据
int length;
LinkList p = NULL, q;
cout << "Input the length:";
cin >> length;
L = (LinkList)malloc(sizeof(struct LNode));
L -> next = NULL;
q = L;
for(int i = 0; i < length; ++ i){
p = (LinkList)malloc(sizeof(struct LNode)); //生成头结点
cin >> p -> data;
q -> next = p;
q = q -> next;
}
p -> next = NULL;
}
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){
//将两个递增的有序链表La和Lb合并为一个递增有序的有序链表Lc
LinkList pa, pb, pc,q;
pa = La -> next;
pb = Lb -> next;
//pa和pb分别是链表La和Lb的工作指针,初始化为响应链表的首元结点
Lc = pc = La; //用La的头结点作为Lc的头结点
while(pa && pb){ //两个链表的La和Lb均未到表尾结点
if(pa -> data < pb -> data){
//取较小者La中的元素,将pa链接在pc的后面,pa指针后移
pc -> next = pa;
pc = pa;
pa = pa -> next;
}
else if(pa -> data > pb -> data){
//取较小者Lb中的元素,将pb链接在pc后面,pb指针后移
pc -> next = pb;
pc = pb;
pb = pb -> next;
}
else{
//相等时取La中的元素,删除Lb中的元素
pc -> next = pa;
pc = pa;
pa = pa -> next;
q = pb -> next;
delete pb;
pb = q;
}
}
pc -> next = pa ? pa : pb; //将非空表的剩余元素直接链接在Lc表的最后
delete Lb; //释放Lb的头结点
}
void ListPrint(LinkList L){
//打印链表
LNode *p;
p = L -> next;
if(L -> next == NULL){
cout << "NULL" << endl;
}
while(p){
cout << p -> data << "\t";
p = p -> next;
}
cout << endl;
}
int main(){
LinkList La, Lb, Lc;
ListRead(La);
ListRead(Lb);
MergeList(La,Lb,Lc);
cout << "合并之后的链表为:" << endl;
ListPrint(Lc);
return 0;
}
网友评论