think: 1顺序建立链表+链表的顺序输出+链表的有序(顺序)归并;链表的元素插入
sdut原题链接
数据结构实验之链表四：有序链表的归并 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
以下为accepted代码
#include <stdio.h> #include <string.h> #include <stdlib.h> struct node { int Data; struct node *next; }; struct node * Build(int n);//顺序建立链表 struct node * ans(struct node *head1, struct node *head2);//链表的有序(顺序)归并 void Pri(struct node *head);//链表的顺序输出 int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { struct node *head1, *head2, *head; head1 = (struct node *)malloc(sizeof(struct node)); head1->next = NULL; head2 = (struct node *)malloc(sizeof(struct node)); head2->next = NULL; head = (struct node *)malloc(sizeof(struct node)); head->next = NULL; head1 = Build(n); //Pri(head1); head2 = Build(m); //Pri(head2); head = ans(head1, head2); Pri(head); } return 0; } void Pri(struct node *head)//链表的顺序输出 { struct node *p; p = head->next; while(p != NULL) { printf("%d%c", p->Data, p->next == NULL? '\n': ' '); p = p->next; } } struct node * Build(int n)//顺序建立链表 { struct node *head, *tail; head = (struct node *)malloc(sizeof(struct node)); head->next = NULL; tail = head; struct node *p; for(int i = 0; i < n; i++) { p = (struct node *)malloc(sizeof(struct node)); scanf("%d", &p->Data); p->next = tail->next; tail->next = p; tail = p; } return head; } struct node * ans(struct node *head1, struct node *head2)//链表的有序(顺序)归并 { struct node *head, *tail; head = (struct node *)malloc(sizeof(struct node)); head->next = NULL; tail = head; struct node *p, *q, *a, *b; p = head1->next; a = head2->next; q = p, b = a; while(p != NULL && a != NULL) { if(p->Data < a->Data) { q = p->next; p->next = tail->next; tail->next = p; tail = p; p = q; if(p == NULL) break; } else { b = a->next; a->next = tail->next; tail->next = a; tail = a; a = b; if(a == NULL) break; } } if(p == NULL) tail->next = a; else if(a == NULL) tail->next = p; free(head1); free(head2); return head; } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 108KB Submit time: 2017-03-10 17:07:53 ****************************************************/