（ 1 ）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个
链表的存储空间，不另外占用其它的存储空间。表中不允许有重复的数据。
#include<stdio.h> typedef struct Lnode{int data;struct Lnode *next;} Lnode,*Link;void createlist(Link &L,int n,int z[]);void listput(Link &L1,Link &L2,Link &L3);main(){ Link a1,a2,a3;int an=5,bn=6;int a[an]={2,4,7,3,9};int b[bn]={5,12,13,1,15,2};createlist(a1,an,a);createlist(a2,bn,b);listput(a1,a2,a3);}void createlist(Link &L,int n,int z[]){Lnode *p,*r,*L1;L=new Lnode; //分配一个Londe类型的动态内存空间，指针变量L指向这个空间地址。L->next=NULL;L1=L;p=new Lnode;p->data=z[0];p->next=NULL;L->next=p;for(int i=1;i<n;i++){r=L;p=new Lnode;p->data=z[i];for(int j=0;j<i;j++){ if(p->data<r->next->data){ p->next=r->next;r->next=p;break;}else{ r=r->next;if(!r->next){ r->next=p; p->next=NULL; }}}}printf("序列：");while(L1->next){L1=L1->next;printf("%d ",L1->data);} printf("\n");}void listput(Link &L1,Link &L2,Link &L3){Lnode *s1,*s2,*r1,*q; s1=L1->next;s2=L2->next;L3=L1; r1=L3;while(s1&&s2){ if(s1->data<s2->data) { r1->next=s1; r1=s1; s1=s1->next; }else if(s1->data>s2->data){ r1->next=s2;r1=s2; s2=s2->next; }else {r1->next=s1;r1=s1; s1=s1->next;q=s2->next;delete s2;s2=q; }}r1->next=s1?s1:s2;/*?:是一个条件运算符,比如P=A?B:C,它表示---若A为真,则用P=B,若A为假,则用P=C.*/delete L2;printf("结果：");while(L3->next){ L3=L3->next; printf("%d ",L3->data);} }
（ 2 ）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍用原
两个链表的存储空间， 不另外占用其它的存储空间。表中允许有重复的数据。
int listreverse(Link &L) //单链表递归倒序输出{L=L->next;Lnode *r;r=L;if(!L)return 0;elselistreverse(L);printf("%d ",r->data); }void listreverse(Lnode *L) //前插法倒序输出 {Lnode *r,*p,*L1;p=L->next;L1=L;L1->next=NULL; while(p) { r=p->next;p->next=L1->next;L1->next=p;p=r;}printf("结果："); while(L1->next) { L1=L1->next; printf("%d ",L1->data); }}
（ 3 ） 巳知两个链表A 和B 分别表示两个集合， 其元素递增排列。请设计算法求出A 与
B 的交集， 并存放于A 链表中。
void listputmix(Link &L1,Link &L2,Link &L3) //两个单链表的交集{Lnode *p1,*p2,*r,*q;p1=L1->next;p2=L2->next;L3=L1;r=L3;while(p1&&p2){if(p1->data<p2->data){ q=p1; p1=p1->next; delete q; }else if(p1->data>p2->data){ q=p2; p2=p2->next; delete q; }else if(p1->data==p2->data){ r->next=p1;r=p1;p1=p1->next;q=p2;p2=p2->next; delete q; }}while(p1) { q=p1; p1=p1->next, delete q; }while(p2) { q=p2; p2=p2->next, delete q; }r->next=NULL;delete L2;printf("结果：");while(L3->next){ L3=L3->next; printf("%d ",L3->data); }}
（ 4 ） 巳知两个链表A 和B 分别表示两个集合， 其元素递增排列。请设计算法求出两个
集合A 和B 的差集（ 即仅由在A 中出现而不在B 中出现的元素所构成的集合），并以同样的
形式存储， 同时返回该集合的元素个数。
int listputdef(Link &L1,Link &L2,Link &L3) //两个单链表的差集（只出现在A中而不在B中出现）{Lnode *p1,*p2,*r,*q;p1=L1->next;p2=L2->next;L3=L1;r=L3;int n=0; while(p1&&p2){if(p1->data<p2->data){ r->next=p1; r=p1; p1=p1->next; n++;}else if(p1->data>p2->data){ q=p2; p2=p2->next; delete q;}else if(p1->data==p2->data){ q=p1;p1=p1->next; delete q; q=p2;p2=p2->next; delete q; }}while(p1) { r->next=p1; r=p1; p1=p1->next; }while(p2) { q=p2; p2=p2->next, delete q; }r->next=NULL; //一定要把最后一个结点的next指向为NULL，因为它原本的next指向的结点已经删除 delete L2;printf("结果：");while(L3->next){ L3=L3->next; printf("%d ",L3->data); }return n;}
（ 5 ） 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C ， 其中
B 表的结点为A 表中值小于零的结点， 而C 表的结点为A 表中值于零的结点（ 链表A 中的
元素为非零整数， 要求B 、C 表利用A 表的结点） 。
#include<stdio.h> //创建结点，作为另一条链表的头节点，前插法输出typedef struct Lnode{int data;struct Lnode *next;} Lnode,*Link;void createlist(Link &L,int n,int z[]);void DifCompose(Link &L);main(){ Link a1;int an=10;int a[an]={-2,5,-6,7,-1,12,-5,8,-9,10};createlist(a1,an,a);DifCompose(a1);}void createlist(Link &L,int n,int z[]){Lnode *p,*r,*L1;L=new Lnode;L->next=NULL;r=L;L1=L;for(int i=0;i<n;i++){p=new Lnode;p->data=z[i];p->next=NULL;r->next=p;r=p;}printf("A：");while(L1->next) { L1=L1->next;printf("%d ",L1->data);} printf("\n");}void DifCompose(Link &L){Lnode *L1,*L2,*p,*r;L2=new Lnode;L2->next=NULL;p=L->next;L1=L;L1->next=NULL;while(p){ r=p->next;if(p->data<0){p->next=L1->next;L1->next=p;}else{p->next=L2->next;L2->next=p;}p=r;}printf("B：");while(L1->next){ L1=L1->next; printf("%d ",L1->data); } printf("\n");printf("C：");while(L2->next){ L2=L2->next; printf("%d ",L2->data);} }void DifCompose(Link &L) //不创建结点，记录另一条链表的首元节点，后插法输出{Lnode *p,*r1,*r2,*L1,*L2;p=L->next;r1=L;L1=L;int n=1;while(p){ if(p->data>0){r1->next=p;r1=p;p=p->next;}else{if(n>0){ r2=p; L2=p; p=p->next;n=0;}else {r2->next=p;r2=p;p=p->next;} }}r1->next=NULL;r2->next=NULL;printf("B：");while(L2){printf("%d ",L2->data);L2=L2->next;} printf("\n");printf("C：");while(L1->next){ L1=L1->next; printf("%d ",L1->data);} }
（ 6 ） 设计一个算法， 通过一趟遍历在单链表中确定值最大的结点。
void listmax(Link &L) //遍历单链表最大值{Lnode *p;int max;p=L->next;max=p->data;while(p->next){p=p->next;if(p->data>max)max=p->data;}printf("最大值：%d",max);}
（ 7 ） 设计一个算法， 通过遍历一趟， 将链表中所有结点的链接方向逆转， 仍利用原表的
存储空间。
void listreverse(Lnode *L) //单链表所有结点的链接方向"原地"逆置{Lnode *r,*p,*q;p=L;r=q=NULL;while(p) //使得原来的每个后一结点指向前一结点，头结点的next指向空{ q=p->next;p->next=r;r=p;p=q;}printf("结果："); while(r->next) { printf("%d ",r->data); r=r->next; }}
（ 8 ） 设计一个算法， 删除递增有序链表中值大于mink 且小于maxk 的所有元素（ mink
和是给定的两个参数， 其值可以和表中的元素相同， 也可以不同）。
void Diflist(Link &L,int mink,int maxk) //无序单链表删除符合条件的元素 {Lnode *p,*r,*L1;L1=L;p=L->next;while(p){r=p->next;if(p->data>mink&&p->data<maxk) {delete p; L1->next=r;}else{L1->next=p;L1=p; }p=r;}while(L->next) { L=L->next;printf("%d ",L->data);} }void Diflist(Link &L,int mink,int maxk) //有序单链表删除符合条件的元素 {Lnode *p,*r,*L1;L1=L;p=L->next;while(p){while(p->data>mink&&p->data<maxk){r=p->next;delete p;p=r;} L1->next=p;L1=p;p=p->next;}while(L->next) { L=L->next;printf("%d ",L->data);} }
（ 9 ） 已知指向双向循环链表中的一个结点， 其结点结构为data 、prior 、next 三个域，
写出算法p 所指向的结点和它的前结点的顺序。
#include<stdio.h> //在双向循环链表中，第n个结点和前驱结点交换位置typedef struct Lnode{int data;struct Lnode *prior;struct Lnode *next;} Lnode,*Link;void createlist(Link &L,int n,int z[]);void change(Link &L,int n); main(){ Link a1;int n=6;int an=10;int a[an]={-2,5,-6,7,-1,12,-5,8,-9,10};createlist(a1,an,a);change(a1,n);}void createlist(Link &L,int n,int z[]){Lnode *p,*r,*L1;L=new Lnode;r=L;L1=L;for(int i=0;i<n;i++){p=new Lnode;p->data=z[i];r->next=p;p->prior=r;r=p;}p->next=L;L->prior=p;printf("双向循环链表：");while(L1->next!=L) { L1=L1->next;printf("%d ",L1->data);} printf("\n");}void change(Link &L,int n){Lnode *p,*r,*k1,*k2,*L1;p=L; L1=L;for(int i=0;i<n;i++) { r=p;p=p->next; }k1=r->prior;k2=p->next;k1->next=p;p->next=r;r->next=k2;k2->prior=r;r->prior=p;p->prior=k1;printf("转变之后链表：");while(L1->next!=L) { L1=L1->next;printf("%d ",L1->data);} }
