#include <stdio.h>
#include <malloc.h>

typedef struct LNode{		//定义结构体 
	int data;
	struct LNode *next;
}Node,*LinkList;

void InitList(LinkList &);	//初始化链表 
void output(LinkList);	//遍历链表 
void merge(LinkList & , LinkList &);	//合并链表 

int main(void){
	LinkList L;
	printf("请输入第一个链表（输入-1表示结束）：");
	InitList(L);
	output(L);
	
	LinkList S;
	printf("请输入第二个链表（输入-1表示结束）：");
	InitList(S);
	output(S);
	
	merge(L,S);
	
	return 0;
}

void InitList(LinkList &L){		//初始化链表 
	L = (Node*)malloc(sizeof(Node));
	L->next = NULL;
	int e;
	Node *p = L;
	scanf("%d",&e);
	while(e != -1){
		Node *s = (Node*)malloc(sizeof(Node));
		s->data = e;
		s->next = p->next;
		p->next = s;
		p = s;
		scanf("%d",&e);
	}
}

void output(LinkList L){	//遍历链表 
	Node *p = L->next;
	printf("当前链表是：");
	while(p != NULL){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

void merge(LinkList &L , LinkList &S){		//合并链表 
	Node *La = L->next;
	Node *Ls = S->next;
	LinkList C = L;
	Node *Lc = L;
	while(La != NULL && Ls != NULL){
		if(La->data <= Ls->data){
			Lc->next = La;
			Lc = La;
			La = La->next;
		}else{
			Lc->next = Ls;
			Lc = Ls;
			Ls = Ls->next;
		}
	}
	if(La != NULL){
		Lc->next = La;
	}
	if(Ls != NULL){
		Lc->next = Ls;
	}
	free(S);
	output(C);
}