Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。
Input
第一行输入M与N的值；
第二行依次输入M个有序的整数；
第三行依次输入N个有序的整数。
Output
输出合并后的单链表所包含的M+N个有序的整数。
Sample Input
6 5
1 23 26 45 66 99
14 21 28 50 100
Sample Output
1 14 21 23 26 28 45 50 66 99 100
Hint
不得使用数组！
Source
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct LNode{
int data;
struct LNode *next;
}*LinkList,LNode;
LinkList createLinkList(LinkList &head,int n){
LNode *tail,*p;
head =tail = (LinkList)malloc(sizeof(LNode));
head->next = NULL;
tail = head;
for (int i=0;i<n;i++)
{
p = (LinkList)malloc(sizeof(LNode));
p->next = NULL;
scanf("%d",&p->data);
tail->next = p;
tail = p;
}
return head;
}
void display(LinkList p){
p=p->next;
while(p){
if (p->next)
{
printf("%d ",p->data);
}else{
printf("%d\n",p->data);
}
p = p->next;
}
}
LinkList merge_LinkList(LinkList list1,LinkList list2){
LNode *p1 = list1->next;
LNode *p2 = list2->next;
list1->next = NULL;
LNode *p,*tail;
tail = list1;
while(p1 && p2){
if (p1->data < p2->data)
{
tail->next = p1;
tail = p1;
**//这里千万不能加tail->next=NULL, 与"tail->next = p1"冲突**
p1 = p1->next;
}else{
tail->next = p2;
tail = p2;
p2 = p2->next;
}
}
if (p1)
{
tail->next = p1;
}
if (p2)
{
tail->next = p2;
}
return list1;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
LinkList linklist = NULL,list2=NULL;
createLinkList(linklist,n);
createLinkList(list2,m);
display(merge_LinkList(linklist,list2));
return 0;
}
