7-6 sdut-C语言实验-有序链表的归并
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。
输入格式:
第一行输入M与N的值；
第二行依次输入M个有序的整数；
第三行依次输入N个有序的整数。
输出格式:
输出合并后的单链表所包含的M+N个有序的整数。
输入样例:
6 5 1 23 26 45 66 99 14 21 28 50 100
输出样例:
1 14 21 23 26 28 45 50 66 99 100
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include <iostream> #include <stdlib.h> using namespace std; typedef struct node pnode; struct node{ int data; struct node* next; }; void put(struct node*L) { L = L->next; int x=0; for(;L!=NULL;L=L->next) { x++; if(x>1) cout<<" "; cout<<L->data; } cout<<endl; } void together(struct node*&L1,struct node*&L2) { struct node* p1 = L1->next,*p2 = L2->next,*tail = L1; while(p1&&p2) { //此处也存在思维点，这样子比思维（两个节点比较，小的接前面，大的接后面，每一轮都这样）方便太多了，省时好用！ if(p1->data<=p2->data) { tail->next = p1; p1 = p1->next; //tail = p1; tail->next->next = NULL; //p1 = p1->next; tail = tail->next; //tail->next = NULL; } else { tail->next = p2; p2 = p2->next; //tail = p2; tail->next->next = NULL; //p2 = p2->next; tail = tail->next; //tail->next = NULL; } } if(p1!=NULL) tail->next = p1; //这样子会使剩余的所有节点都会接上，简洁好用 if(p2!=NULL) tail->next = p2; } int main() { int m,n; while(cin>>m>>n) { struct node* L1,*p1,*tail1; L1 = (pnode*)malloc(sizeof(pnode)); L1->next = NULL; tail1 = L1; struct node* L2,*p2,*tail2; L2 = (pnode*)malloc(sizeof(pnode)); L2->next = NULL; tail2 = L2; int x; for(int i=0;i<m;i++) { cin>>x; p1 = (pnode*)malloc(sizeof(pnode)); p1->next = NULL; p1->data = x; tail1->next = p1; tail1 = tail1->next; } for(int i=0;i<n;i++) { cin>>x; p2 = (pnode*)malloc(sizeof(pnode)); p2->next = NULL; p2->data = x; tail2->next = p2; tail2 = tail2->next; } together(L1,L2); put(L1); } }
