归并两个递增序列链表为一个递减有序链表
时限：1000ms 内存限制：10000K 总时限：3000ms
描述
假设有两个按元素值递增有序排列的线性表a和b，均以单链表作为存储结构，请编程实现将表a和表b归并成一个按元素值递减有序排列的线性表c（注意：非严格递减，也就是说本题中的数据有可能相等），并要求利用原表的结点空间构造c表。
输入
第一行先输入两个小于100的正整数m，n，第二行从小到大的输入m个整数，第三行从小到大的输入n个整数。
输出
归并这两个序列为一个递减的序列c，用链表存储，之后输出按顺序输出链表c的值，每个数占一行。
输入样例
4 3 2 6 6 10 3 10 50
输出样例
50 10 10 6 6 3 2
#include <stdio.h> #include <stdlib.h> typedef struct Lnode { int data; struct Lnode *next; }Lnode,*LinkList; LinkList CreateList(LinkList L,int n) { LinkList p,s; p=L=(LinkList)malloc(sizeof(Lnode)); for(;n>0;n--) { s=(LinkList)malloc(sizeof(Lnode)); scanf("%d",&s->data); p->next=s; p=s; } p->next=NULL; return L; } LinkList CombineList(LinkList L) { LinkList pa=NULL,pb=NULL,pc=NULL,La,Lb; int m,n; scanf("%d",&m); scanf("%d",&n); La=CreateList(L,m); Lb=CreateList(L,n); pa=La->next; pb=Lb->next; pc=L=(LinkList)malloc(sizeof(Lnode)); while(pa&&pb) { if(pa->data<pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } } while(pa) { pc->next=pa; pc=pa; pa=pa->next; } while(pb) { pc->next=pb; pc=pb; pb=pb->next; } return L; } /*LinkList InverseList(LinkList L) { LinkList p,L1; p=L=CombineList(L); L1=L->next; while(L1) { L->next=L1->next; L1->next=p; p=L1; L1=L->next; } return p; } */ LinkList InverseList(LinkList L) { LinkList p,q=NULL; L=CombineList(L); p=L->next; while(p->next->next) { q=p->next; p->next=q->next; q->next=L->next; L->next=q; } p->next->next=L->next; L->next=p->next; p->next=NULL; return L; } int main() { LinkList Lc=NULL,p,L=NULL; Lc=InverseList(L); p=Lc->next; while(p) { printf("%d\n",p->data); p=p->next; } return 0; }
