【数据结构】链表合并

Tags:

Description

大家已经学习过了链表，现在考虑这样一个问题：对于给定的两条有头节点的有序递增链 表，你需要将他合并成一条有头节点的有序递增链表。 
 
另外，新的链表上的每个节点均为原来的两条链表上的节点，即在合并完成之后，原来的 两条两边变成空链表。 
 
操作如图所示 

你只需要提交 List merge(List L1,List L2)函数即可
主体代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
	ElementType Data;
	PtrToNode   Next;
};
typedef struct Node Node;
typedef PtrToNode List;

List Read()
{
	List head = (List)malloc(sizeof (Node));
	head->Next = NULL;
	List now = head;
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		List tmp = (List)malloc(sizeof(Node));
		tmp->Next = NULL;
		scanf("%d", &tmp->Data);
		now->Next = tmp;
		now = now->Next;
	}
	return head;
}
void Print(List L)
{
	int cot = 0;
	List now = L->Next;
	while (now)
	{
		if (cot)printf(" ");
		cot++;
		printf("%d", now->Data);
		now = now->Next;
	}
	if (!cot)printf("NULL");
	printf("\n");
}


List Merge(List L1, List L2);


int main()
{
	List L1, L2, L;
	L1 = Read();
	L2 = Read();
	L = Merge(L1, L2);
	Print(L);
	Print(L1);
	Print(L2);
	return 0;
}
/*你的代码会被嵌在这里*/