C++ 单链表合并算法：不破坏原链表的合并操作

问题描述:

给定两个线性表 L1=(x1,x2,...xn) 和 L2=(y1,y2,...ym)，采用带头节点的单链表存储。设计一个算法将 L1 和 L2 合并成一个新的线性表 L3，L3 仍采用单链表存储，要求不破坏原有的两个链表。

合并结果:

若 m <= n，则 L3=(x1,y1,x2,y2,...xm,ym,xm+1,...xn)
若 m > n，则 L3=(x1,y1,x2,y2,...xn,yn,xn+1,...xm)

代码实现:

#include <malloc.h>
#include <stdio.h>
#include<iostream>
using namespace std;
const int MAXSIZE=100;
typedef int ElemType;
typedef struct node
{	ElemType data;					//数据域
	struct node *next;				//指针域
} SLinkNode;						//单链表结点类型
void InitList(SLinkNode *&L)					//初始化单链表L
{	L=(SLinkNode *)malloc(sizeof(SLinkNode));	//创建头结点L
	L->next=NULL;
}
void DestroyList(SLinkNode *&L)		//销毁单链表L
{	SLinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{	free(pre);
		pre=p; p=p->next;			//pre、p同步后移
	}
	free(pre);
}
int GetLength(SLinkNode *L)			//求长度
{	int i=0;
	SLinkNode *p=L->next;
	while (p!=NULL)
	{	 i++;
		p=p->next;
	}
	return i;
}
int GetElem(SLinkNode *L,int i,ElemType &e)	//求第i个结点值
{	int j=0;
	SLinkNode *p=L;					//p指向头结点，计数器j置为0
	if (i<=0) return 0;				//参数i错误返回0
	while (p!=NULL && j<i)
	{	 j++;
		p=p->next;
	}
	if (p==NULL)
		return 0;					//未找到返回0
	else
	{	 e=p->data;
		return 1;					//找到后返回1
	}
}
int Locate(SLinkNode *L,ElemType e)	//求第一个值为e的结点位置
{	SLinkNode *p=L->next;
	int j=1;						//p指向第一个数据结点，j置为其序号1
	while (p!=NULL && p->data!=e)
	{	 p=p->next;
		j++;
	}
	if (p==NULL) return(0);			//未找到返回0
	else return(j);					//找到后返回其序号
}
int InsElem(SLinkNode *&L,ElemType x,int i)	//插入结点值为x的结点
{	int j=0;
	SLinkNode *p=L,*s;
	if (i<=0) return 0;				//参数i错误返回0
	while (p!=NULL && j<i-1)		//查找第i-1个结点p
	{	 j++;
		p=p->next;
	}
	if (p==NULL)
		return 0;					//未找到第i-1个结点时返回0
	else							//找到第i-1个结点p
	{	 s=(SLinkNode *)malloc(sizeof(SLinkNode));
		s->data=x;					//创建存放元素x的新结点s
		s->next=p->next;			//将s结点插入到p结点之后
		p->next=s;
		return 1;					//插入运算成功,返回1
	}
}
int DelElem(SLinkNode *&L,int i)	//删除结点
{	int j=0;
	SLinkNode *p=L,*q;
	if (i<=0) return 0;				//参数i错误返回0
	while (p!=NULL && j<i-1)		//查找第i-1个结点
	{	 j++;
		p=p->next;
	}
	if (p==NULL)
		return 0;					//未找到第i-1个结点时返回0
	else							//找到第i-1个结点p
	{	 q=p->next;					//q指向被删结点
		if (q==NULL)
			return 0;				//没有第i个结点时返回0
		else
		{	 p->next=q->next;		//从单链表中删除q结点
			free(q);				//释放其空间
			return 1;
		}
	}
}
void DispList(SLinkNode *L)			//输出单链表
{	SLinkNode *p=L->next;
	while (p!=NULL)
	{	 printf('%d ',p->data);
		p=p->next;
	}
	printf('
');
}

void CreateListF(SLinkNode *&L,ElemType a[],int n)	//头插法建表
{	SLinkNode *s;  int i;
	L=(SLinkNode *)malloc(sizeof(SLinkNode));		//创建头结点
	L->next=NULL;									//头结点的next域置空
	for (i=0;i<n;i++)								//遍历a数组所有元素
	{	 s=(SLinkNode *)malloc(sizeof(SLinkNode));
		s->data=a[i];								//创建存放a[i]元素的新结点s
		s->next=L->next;							//将s插在头结点之后
		L->next=s;
	}
}

void CreateListR(SLinkNode *&L,ElemType a[],int n)	//尾插法建表
{	SLinkNode *s,*tc;  int i;
	L=(SLinkNode *)malloc(sizeof(SLinkNode));		//创建头结点
	tc=L;											//tc为L的尾结点指针
	for (i=0;i<n;i++)
	{	 s=(SLinkNode *)malloc(sizeof(SLinkNode));
		s->data=a[i];								//创建存放a[i]元素的新结点s
		tc->next=s;									//将s结点插入tc结点之后
		tc=s;
	}
	tc->next=NULL;									//尾结点next域置为NULL
}

//开始补充代码
// 在此处补充你的代码
int main()
{
	SLinkNode *L1,*L2,*L3;
	int n,m,a[MAXSIZE],b[MAXSIZE];
	cin>>n;
	for(int i=0;i<n;i++)
	  cin>>a[i];
	CreateListR(L1,a,n);				//尾插法建表
	cin>>m;
	for(int i=0;i<m;i++)
	  cin>>b[i];
	CreateListR(L2,b,m);				//尾插法建表
	Merge(L1,L2,L3);
    DispList(L3);
	DestroyList(L1);
	DestroyList(L2);
	DestroyList(L3);
}

补充代码:

void Merge(SLinkNode *L1, SLinkNode *L2, SLinkNode *&L3) {
    L3 = (SLinkNode *)malloc(sizeof(SLinkNode));  // 创建头结点
    L3->next = NULL;
    SLinkNode *p1 = L1->next;
    SLinkNode *p2 = L2->next;
    SLinkNode *p3 = L3;  // p3指向L3的尾结点
    while (p1 != NULL && p2 != NULL) {
        p3->next = p1;
        p1 = p1->next;
        p3 = p3->next;
        p3->next = p2;
        p2 = p2->next;
        p3 = p3->next;
    }
    if (p1 != NULL) {
        p3->next = p1;
    }
    if (p2 != NULL) {
        p3->next = p2;
    }
}

算法说明:

创建一个新的头结点 L3，并初始化其 next 指针为 NULL。
使用三个指针 p1、p2 和 p3 分别指向 L1、L2 和 L3 的第一个数据结点。
循环遍历 L1 和 L2，将 p1 和 p2 指向的结点交替插入 L3 中，直到其中一个链表为空。
如果 L1 还有剩余结点，则将剩余的结点插入到 L3 的末尾。
如果 L2 还有剩余结点，则将剩余的结点插入到 L3 的末尾。

测试用例:

输入:

输出:

1 2 3 4 5 6 7 8 9

样例输入:

样例输出:

1 2 3 4 5 6 7 8 9

总结:

该算法实现了将两个单链表合并成一个新的单链表，并保证了原链表的完整性。该算法的时间复杂度为 O(m+n)，空间复杂度为 O(1)。