将两个链表表示的递增整数序列合并为一个递增的整数序列.本人的合并函数出错在哪里

码拜

10年 ago

目前在写作业的时候遇到了这样一题作业部分的代码就是合并函数
作业是在PTA平台写的只要求写一个合并函数
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */
List Merge( List L1, List L2 )
{
List pa=L1->Next,pb=L2->Next,q,r=L1;
while(pa!=NULL&&pb!=NULL)
{
if(pa->Data<pb->Data)
{
r->Next=pa;
r=pa;
pa=pa->Next;
}
else
{
r->Next=pb;
r=pb;
pb=pb->Next;
}
}
if(pa!=NULL)
q=pa;
if(pb!=NULL)
q=pb;
r->Next=q;
return L1;
}
int main()
{
List L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
return 0;
}
List Merge函数本人不知道哪里出了问题找了很久
希望有前辈指点一下非常感谢

解决方案

写了个简单的Read和Print函数，合并后结果感觉并没有问题
注意点：
1.题主的写法说明链表是带头结点的
2.合并后，虽然L没有问题，但是你已经改变了原来的L1和L2的结点

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
	ElementType Data;
	PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */
List Read()
{
	List a = (List)malloc(sizeof(struct Node));
	a->Next = NULL;
	List p = a;
	ElementType temp;
	scanf("%d", &temp);
	while(temp != 0)
	{
		List cur = (List)malloc(sizeof(struct Node));
		cur->Data = temp;
		cur->Next = NULL;
		p->Next = cur;
		p = cur;
		scanf("%d", &temp);
	}
	return a;
}
void Print( List L )
{
	L = L->Next;
	while(L)
	{
		printf("%d ", L->Data);
		L = L->Next;
	}
	printf("\n");
}
List Merge( List L1, List L2 )
{
	List pa=L1->Next,pb=L2->Next,q,r=L1;
	while(pa!=NULL&&pb!=NULL)
	{
		if(pa->Data<pb->Data)
		{
			r->Next=pa;
			r=pa;
			pa=pa->Next;
		}
		else
		{
			r->Next=pb;
			r=pb;
			pb=pb->Next;
		}
	}
	if(pa!=NULL)
		q=pa;
	if(pb!=NULL)
		q=pb;
	r->Next=q;
	return L1;
}
int main()
{
	List L1, L2, L;
	L1 = Read();
	L2 = Read();
	L = Merge(L1, L2);
	printf("合并后:");
	Print(L);
	printf("L1:");
	Print(L1);
	printf("L2:");
	Print(L2);
	return 0;
}

照顾各种极端情况：
空链表
链表长度为1
链表中有值相同的整数
链表中的全部值均相等
……