博客

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出

NULL

。

输入样例:

1 3 5 -1
2 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

#include <stdio.h>
#include <stdlib.h>
typedef struct node* node;
struct node{
	int data;
	struct node* next;
}; 
node initlist()
{
	node head=(node)malloc(sizeof(struct node));
	head->next=NULL;
	return head;
}
void creat(node *L){
	node s,r=L;
	int num,flag=1;
	while(flag)
	{
		scanf("%d",&num);
		if(num>=0)
		{
			s=(node)malloc(sizeof(struct node));
			s->data=num;
			r->next=s;
			r=r->next;
		}
		else{
			flag=0;
			r->next=0;
		}
	}
}
void print(node L)
{
	node t=L->next;
	int flag=1;int num=0;
	while(t!=NULL)
	{
		num++;
		if(flag){
			printf("%d",t->data);
			flag=0;
		}
		else{
			printf(" %d",t->data);
		}
		t=t->next;
	}
	if(num==0)printf("NULL");
}
void resolve(node L1,node L2,node L3)
{
	node s1=L1->next;
	node s2=L2->next;
	node s3=L3;
	while(s1!=NULL&&s2!=NULL)
	{
		if(s1->data<s2->data){
			s3->next=s1;
			s3=s3->next;
			s1=s1->next;
		}
		else{
			s3->next=s2;
			s3=s3->next;
			s2=s2->next;
		}
	}
	if(s1!=NULL)s3->next=s1;
	if(s2!=NULL)s3->next=s2;
}
int main(){
	node L1,L2,L3;
	L1=initlist();
	L2=initlist();
	L3=initlist();
	creat(L1);
	creat(L2);
	resolve(L1,L2,L3);
	print(L3);
}