数据结构实验之链表四：有序链表的归并 (sdut oj)

数据结构实验之链表四：有序链表的归并

Time Limit: 1000MS  Memory Limit: 65536KB

Problem Description

分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。

Input

第一行输入M与N的值；  第二行依次输入M个有序的整数； 第三行依次输入N个有序的整数。

Output

输出合并后的单链表所包含的M+N个有序的整数。

Example Input

6 5 1 23 26 45 66 99 14 21 28 50 100

Example Output

1 14 21 23 26 28 45 50 66 99 100

Hint

不得使用数组！

Author

参考代码

#include<stdio.h> #include<stdlib.h> struct node { int data; struct node *next; }; int main() { int n,m; struct node *head1,*head2,*tail,*p,*q; head1 = (struct node *)malloc(sizeof(struct node)); head2 = (struct node *)malloc(sizeof(struct node)); head1->next = head2->next =NULL; scanf("%d%d",&n,&m); tail = head1; while(n--) { p = (struct node *)malloc(sizeof(struct node)); scanf("%d",&p->data); p->next = tail->next; tail->next = p; tail = p; } tail = head2; while(m--) { p = (struct node *)malloc(sizeof(struct node)); scanf("%d",&p->data); p->next = tail->next; tail->next = p; tail = p; } p = head1->next; q = head2->next; tail = head1; head1->next = head2->next = NULL; while( p && q ) { if( p->data > q->data ) { tail->next = q; tail = q; q = q->next; } else { tail->next = p; tail = p; p = p->next; } } if(p) { tail->next = p; } else { tail->next = q; } p = head1->next; printf("%d",p->data); p = p->next; while(p) { printf(" %d",p->data); p = p->next; } printf("\n"); return 0; }