[数据结构与算法]数据结构考题 两个有序链表的合并 (25 分)

已知两个非递减有序单链表La与Lb，编写程序把La和Lb合并为新的非递减有序链表Lc。

单链表的类型描述：

typedef int ElemType;
typedef struct lnode
{ ElemType data;
  struct lnode *next;
 }Lnode,*LinkList;

输入格式:

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

输出格式:

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

输入样例:

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

结尾无空行

输出样例:

1 2 3 4 5 6 8 10

结尾无空行

输入样例:

-1
-1

结尾无空行

输出样例:

NULL

结尾无空行

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;
    struct node* next;
};
typedef struct node* Pre;
int main()
{
    int n;
    Pre head = (Pre)malloc(sizeof(struct node));
    head->data = 0;
    head->next = NULL;
    Pre p,q;
    p  =  q  =  head; 
	while(scanf("%d",&n),n != -1){
   		Pre t = (Pre)malloc(sizeof(struct node));
		head->next = t;
		t->data = n;
		t->next = NULL;
		head = head->next;
}
	while(scanf("%d",&n),n != -1){
        while(p->next != NULL){
    		if(p->next->data >= n){
        		Pre tmp = (Pre)malloc(sizeof(struct node));
        		tmp->next = p->next;
    			tmp->data = n;
    			p->next = tmp;
    			break;
        	}
    else p = p->next;
}
	if(p->next == NULL){
    	Pre x = (Pre)malloc(sizeof(struct node));
 
    	x->data = n;
    	x->next = NULL;
    	p->next = x;
    }
}
	if(q->next == NULL)
		printf("NULL");
	else{
        q = q->next;
	while(q->next != NULL){
    printf("%d ",q->data);
	q = q->next;
}
	printf("%d",q->data);
}
    return 0;
}