MergeSortedList

#include<stdio.h> #include<stdlib.h> typedef struct LinkNode{ int val; LinkNode* next; }*LinkList; //不带头结点 LinkNode* CreateLink(int n){ LinkList l=NULL;; if(n<=0){ printf("链表为空\n"); return NULL; } l=(LinkNode*)malloc(sizeof(LinkNode)); if(!l){ printf("overflow!"); exit(1); } printf("请输入结点的值\n"); scanf("%d",&l->val); l->next=NULL; LinkNode *p,*q; q=l; for(int i=1;i<n;i++){ p=(LinkNode*)malloc(sizeof(LinkNode)); if(!l){ printf("overflow!"); exit(1); } printf("请输入结点的值\n"); scanf("%d",&p->val); p->next=q->next; q->next=p; q=p; } return l; } //进行递归进行合并 LinkList MergeList(LinkList la,LinkList lb){ if(la==NULL) return lb; if(lb==NULL) return la; LinkList lc=NULL; if(la->val<lb->val){ lc=la; lc->next=MergeList(la->next,lb); } if(la->val>lb->val){ lc=lb; lc->next=MergeList(la,lb->next); } return lc; } //非递归进行合并 LinkList MergeListAgain(LinkList la,LinkList lb){ LinkNode* pa=la; LinkNode* pb=lb; LinkNode* pc; LinkList lc=NULL; if(la==NULL) return lb; if(lb==NULL) return la; if(pa->val<pb->val){ lc=pa; pa=pa->next; } else{ lc=pb; pb=pb->next; } pc=lc; while(pa&&pb){ if(pa->val<pb->val){ pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } } if(pa) pc->next=pa; if(pb) pc->next=pb; return lc; } void Print(LinkList l){ LinkNode *p=l; while(p){ printf("%3d",p->val); p=p->next; } printf("\n"); } void main(){ int n; LinkList la,lb,lc; printf("请输入链表la节点的个数\n"); scanf("%d",&n); la=CreateLink(n); printf("请输入链表lb节点的个数\n"); scanf("%d",&n); lb=CreateLink(n); lc=MergeListAgain(la,lb); Print(lc); }