算法思想：设f(L,x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点， 显然有f(L->next,x)的功能是删除以L->next为首结点指针的单链表中所有值等于x的结点， 由此可以推出递归模型如下: 终止条件：f(L,x)=不做任何事情； //若L为空表 递归主体：f(L,x)=删除*L结点；f(L->next,x) //若L->data=x f(L,x)=f(L->next,x); //其他情况
LinkList Del_X_3(LinkList &L,ElemType x){ LNode *p; //p指向待删除结点 if(L==NULL){ //递归出口 return; } if(L->data==x){ //若L所指结点的值为x p=L; //删除*L，并让L指向下一个结点 L=L->next; free(p); Del_X(L,x); //递归调用 } else{ //若L所指结点的值不为x Del_X(L->next,x); //递归调用 } }算法思想1：用p从头至尾扫描单链表，pre指向*p结点的前驱。若p所指结点的值为x，则删除，并让p移向下一个结点， 否则让pre、p指针同步后移一个结点。
void Del_X_1(LinkList &L,ElemType x){ LNode *p=L->next,*pre=L,*q; while(p!=NULL){ if(p->data==x){ q=p; p=p->next; pre->next=p; free(p); } else{ pre=p; p=p->next; } } }算法思想2：采用尾插法建立单链表。用p指针扫描L的所有结点，当其职不为x时将其链接到L之后，否则将其释放
void Del_X_2(LinkList &L,ElemType x){ LNode *p=L->next,*pre=L,*q; while(p!=NULL){ if(p->data!=x){ pre->next=p; pre=p; p=p->next; } else{ q=p; p=p->next; free(q); } } pre->next=NULL; }算法思想：用p从头至尾扫描单链表，pre指向p结点的前驱，用minp保存值最小的结点指针(初值为p)，minpre指向minp结点的前驱(初值为pre)。一边扫描，一边比较，若p->data小于minp->data,则将p、pre分别赋值给minp、minpre，如下图所示。当p扫描完毕，minp指向最小值结点，minpre指向最小值结点的前驱结点，再将minp所指结点删除即可。
LinkList Delete_Min(LinkList &L){ LNode *pre=L,*p=pre->next; LNode *min=p,*minpre=pre; while(p!=NULL){ if(p->data<min->data){ minpre=pre; min=p; } pre=p; p=p->next; } minpre->next=min->next; free(min); return L; }算法思想1：将头结点摘下，然后从第一个结点开始，依次插入到头结点的后面(头插法建立单链表),直到最后一个结点为止，这样就实现了链表的逆置。
LinkList Reverse_1(LinkList &L){ LNode *p,*q; //p为工作指针，q为p的后继，以防断链 p=L->next; //从第一个元素结点开始 L->next=NULL; //先将头结点L的next置为NULL while(p!=NULL){ //依次将元素结点摘下 q=p->next; //暂存p的后继 p->next=L->next; //将p结点插入到头结点之后 L->next=p; p=q; } return L; }算法思想2：假设pre、p和r指向3个相邻的结点，假设经过若干操作后，pre之前的结点的指针都已调整完毕，它们的next都指向其原前驱结点。 现在另p结点的next域指向*pre结点，注意到一旦调整指针的指向后，p的后继结点的链就会断开，为此需要用r来指向原p的后继结点。 处理时需要注意两点： 一是在处理第一个结点时，应将其next域置为NULL，而不是指向头结点(因为它将作为新表的尾结点)； 二是在处理完最后一个结点后，需要将头结点的指针指向它。
LinkList Reverse_2(LinkList L){ LNode *pre,*p=L->next,*r=p->next; p->next=NULL; //处理第一个结点 while(r!=NULL){ //r为空，则说明p为最后一个结点 pre=p; //依次继续遍历 p=r; r=r->next; p->next=pre; //指针反转 } L->next=p; //处理最后一个结点 return L; }算法思路：采用直接插入排序算法的思想，先构成只含一个数据节点的有序单链表， 然后依次扫描单链表中剩下的结点p(直至p=NULL为止)，在有序表中通过比较查找插入p的前驱结点pre，然后将p插入到pre之后
void Sort(LinkList &L){ LNode *p=L->next,*pre; LNode *r=p->next; //r保持*p后继结点指针，以保证不断链 p->next=NULL; //构造只含一个数据结点的有序表 p=r; while(p!=NULL){ r=p->next; //保存*p的后继结点指针 pre=L; while(pre->next!=NULL && pre->next->data < p->data){ pre=pre->next; //在有序表中查找插入*p的前驱结点*pre } p->next=pre->next; //将*p插入到*pre之后 pre->next=p; p=r; //扫描原单链表中剩下的结点 } }算法思路：8. 解答： 两个单链表有公共结点，即两个链表从某一结点开始，它们的next 都指向同一个结点。由 于每个单链表结点只有一个next域，因此从第一个公共结点开始，之后它们所有的结点都是重合的，不可能再出现分叉。所以两个有公共结点而部分重合的单链表，拓扑形状看起来像Y,不可能像X. 本题极容易联想到“蛮”方法：在第一个链表上顺序遍历每个结点，每遍历一个结点，在第 二个链表上顺序遍历所有结点，若找到两个相同的结点，则找到了它们的公共结点。显然，该算法的时间复杂度为O(len1xlen2). 接下来我们试着去寻找一个线性时间复杂度的算法。先把问题简化：如何判断两个单向链表 有没有公共结点？应注意到这样一个事实：若两个链表有一个公共结点，则该公共结点之后的所有结点都是重合的，即它们的最后一个结点必然是重合的。因此，我们判断两个链表是不是有重合的部分时，只需要分别遍历两个链表到最后一个结点。若两个尾结点是一样的，则说明它们有公共结点，否则两个链表没有公共结点。 然而，在上面的思路中，顺序遍历两个链表到尾结点时，并不能保证在两个链表上同时到达 尾结点。这是因为两个链表长度不一定一样。但假设一个链表比另一个长k个结点，我们先在长的链表上遍历k个结点，之后再同步遍历，此时我们就能保证同时到达最后一个结点。由于两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的，因此它们肯定也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。 根据这一思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长 的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。此时，该方法的时间复杂度为O(len1+len2). 本题代码如下：
LinkList Search_1st_Common(LinkList L1,LinkList L2){ int len1=Length(L1),len2=Length(L2); //计算两个链表的表长 LinkList longList,shortList; //分别指向表长较长和较短的链表 if(len1>len2){ //L1表长较长 longList=L1->next; shortList=L2->next; dist=len1-len2; //表长之差 } else{ //L2表长较长 longList=L2->next; shortList=L1->next; dist=len2-len1; //表长之差 } while(dist--){ //表长的链表先遍历到第dist个结点，然后同步 longList=longList->next; } while(longList!=NULL){ //同步寻找共同结点 if(longList==shortList){ //找到第一个公共结点 return longList; } else{ //继续同步寻找 longList=longList->next; shortList=shortList->next; } } return NULL; }算法思想:对链表进行遍历,在每次遍历中找出整个链表的最小值元素,输出并释放结点所 占空间:再查找次小值元素,输出并释放空间,如此下去,直至链表为空,最后释放头结点所占 存储空间。该算法的时间复杂度为O(n2)
void Min_Delete(LinkList &head){ while(head->next!=NULL){ LNode *pre,*p,*min,*premin,*u; //循环到只剩头结点 pre=head; //pre为元素最小值结点的前驱结点的指针 p=pre->next; //p为工作指针 min=head->next; while(p!=NULL){ if(p->data < min->data){ min=p; premin=pre; } pre=p; //记住当前最小值结点的前驱 p=p->next; } printf("%d ",min->data); //输出元素最小值结点的数据 premin->next=premin->next->next; //删除元素最小的结点释放结点空间。 free(min); } free(head); //释放头结点 }算法思想：设置一个访问序号变量(初值为0)，每访问一个结点序号自动加1，然后根据序号的奇偶性将结点插入到A表或B表中，重复以上操作直到表尾
LinkList DisCreate_1(LinkList &A){ int i=0; //i记录表A中结点的序号 LinkList B=(LinkList)malloc(sizeof(LNode)); //创建B表表头 B->next=NULL; //B表的初始化 LNode *ra=A,*rb=B,*p; //ra和rb将分别指向将创建的A表和B表的尾结点 p=A->next; //p为链表工作指针，指向待分解的结点 A->next=NULL; //置空新的A表 while(p!=NULL){ i++; if(i%2==0){ //处理序号为偶数的链表结点 rb->next=p; //在B表表尾插入新结点 rb=p; //rb指向新的尾结点 } else{ ra->next=p; ra=p; } p=p->next; //将p恢复为指向新的待处理结点 } ra->next=NULL; rb->next=NULL; return B; }算法，将其拆分为两个线性表，使得A={a1,a2,···,an},B={bn,···,b2,b1}. 算法思想：采用上题思路，不设序号变量。二者的差别仅在于对B表的建立不采用尾插法，而是头插法
LinkList DisCreate_2(LinkList &A){ LinkList B=(LinkList)malloc(sizeof(LNode)); //创建B表头 B->next=NULL; //B表的初始化 LNode *p=A->next,*q; //p为工作指针 LNode *ra=A; //ra始终指向A的尾结点 while(p!=NULL){ ra->next=p; //将*p链到A的表尾 ra=p; p=p->next; if(p!=NULL){ q=p->next; //头插后，*p将断链，因此用q记忆*p的后继 } p->next=B->next; //将*p插入到B的前端 B->next=p; p=q; } ra->next=NULL; //A尾结点的next置空 return B; }算法思想：由于是有序表，所有相同值域的结点都是相邻的，用p扫描递增单链表L， 若*p结点的值域等于其后继结点的值域，则删除后者，否则p移向下一个结点。
void Del_Same(LinkList &L){ LNode *p=L->next,*q; //p为扫描工作指针 if(p==NULL){ return; } while(p->next!=NULL){ q=p->next; //q指向*p的后继结点 if(p->data==q->data){ //找到重复值的结点 p->next=q->next; //释放*q结点 free(q); //释放相同元素值的结点 } else{ p=p->next; } } }算法思想：两个链表已经按元素值递增次序排序,将其合并时,均从第一个结点起进行比较, 将小的结点链入链表中,同时后移工作指针。该问题要求结果链表按元素值递减次序排列,故新 链表的建立应该采用头插法。比较结束后,可能会有一个链表非空,此时用头插法将剩下的结点 依次插入新链表中即可。
void MergeList(LinkList &La,LinkList &Lb){ LNode *r,*pa=La->next,*pb=Lb->next; La->next=NULL; //La作为结果链表的头指针，先将结果链表初始化为空 while(pa && pb){ //当两链表均不为空时，循环 if(pa->data <= pb->data){ r=pa->next; //r暂存pa的后继结点指针 pa->next=La->next; La->next=pa; //将pa结点链于结果表中，同时逆置(头插法) pa=r; //恢复pa为当前待比较结点 } else{ r=pb->next; //r暂存pb的后继结点指针 pb->next=La->next; La->next=pb; //将pb结点链于结果表中，同时逆置(头插法) pb=r; //恢复pb为当前待比较结点 } } if(pa){ pb=pa; //通常情况下会剩一个链表非空,处理剩下的部分 } while(pb){ //处理剩下的一个非空链表 r=pb->next; //依次插入到La中(头插法) pb->next=La->next; La->next=pb; pb=r; } free(Lb); }算法思想:表A、B都有序,可从第一个元素起依次比较A、B两表的元素,若元素值不等, 则值小的指针往后移,若元素值相等,则创建一个值等于两结点的元素值的新结点,使用尾插法 插入到新的链表中,并将两个原表指针后移一位,直到其中一个链表遍历到表尾
void Get_Common(LinkList A,LinkList B){ LinkList C=(LinkList)malloc(sizeof(LNode)); //建立表C C->next=NULL; LNode *La=A->next,*Lb=B->next,*Lc=C; //Lc始终指向C的尾结点 while(La!=NULL && Lb!=NULL){ //循环跳出条件 if(La->data==Lb->data){ //找到公共结点 LinkList node=(LinkList)malloc(sizeof(LNode)); node->data=La->data; //复制产生结点*node Lc->next=node; //将node链接到C上 Lc=node; La=La->next; //A和B继续向后扫描 Lb=Lb->next; } else if(La->data < Lb->data){ La=La->next; //若A的当前元素较小，后移指针 } else{ Lb=Lb->next; //若B的当前元素较小，后移指针 } } }