数据结构——有序单链表原地合并（C语言）

将两个有序单链表进行合并，合并结果仍有序。（合并过程不占用其他存储空间） #include<stdio.h> #include<stdlib.h> #define MAXSIZE 10010 #define ElemType int typedef struct LNode{ ElemType data; LNode *next; }LNode,*LinkList; //创建 LinkList initLinkList(int num){ LNode* head=(LNode *)malloc(sizeof(LNode)); LinkList p=head; p->next=NULL; int elem; while(num--){ printf("输入："); scanf("%d",&elem); LNode* L=(LNode *)malloc(sizeof(LNode)); L->data=elem; L->next=NULL; p->next=L; p=p->next; } return head; } //合并 void CombinationLinkList(LinkList &l1,LinkList &l2,int &flag){ LinkList now1=l1->next; LinkList now2=l2->next; LinkList nx1,nx2; //now的下一个位置 nx1=now1->next; nx2=now2->next; while(now1&&now2){ //如果表1中now1所指向的元素小于表2中now2所指向的元素 if((now1->data) < (now2->data)){ //判断now1所指向的元素的下一个位置的值是否小于now2 //如果不是，这将指针now1和nx1向后移动到元素值小于表2中now2所指向的元素的值 //的位置 while((now1->next)&&(now1->next->data) < (now2->data)){ now1=now1->next; nx1=nx1->next; } //连接结点 now1->next=now2; now1=nx1; //判断是否遍历到表1结束位置 //如果不是，则继续移动nx指针 if(nx1) nx1=nx1->next; flag=1; }else{ while((now2->next)&&(now2->next->data) < (now1->data)){ now2=now2->next; nx2=nx2->next; } now2->next=now1; now2=nx2; if(nx2) nx2=nx2->next; } } } //打印 void display(LinkList p){ LinkList pp=p->next; while(pp){ int data=pp->data; printf("%d ",data); pp=pp->next; } } int main(){ printf("输入元素个数："); int num; scanf("%d",&num); printf("初始化链表1：\n"); LinkList LL1=initLinkList(num); printf("\n打印链表1：\n"); display(LL1); printf("\n初始化链表2：\n"); LinkList LL2=initLinkList(num); printf("\n打印链表2：\n"); display(LL2); printf("\n两表合并\n"); int flag=0; CombinationLinkList(LL1,LL2,flag); if(flag){ display(LL1); }else{ display(LL2); } return 0; }