1、實(shí)現(xiàn)單鏈表逆置無頭結(jié)點(diǎn)：1#include<stdio.h>2#include<stdlib.h>34typedefstructnode{5intdata;6structnode*next;7}Node;89//創(chuàng)建鏈表10Node*CreateList(void){11intval,i,n;12Node*head,*p,*q;1314head=NULL;15printf("請輸入您要建立的鏈表長度:\n");16scanf("%d",&n);17printf("請輸入您要輸入的數(shù)據(jù):\n");18for(i=0;i<n;i++){19scanf("%d",&val);20p=(Node*)malloc(sizeof(Node));21p->data=val;22if(head==NULL)23head=q=p;24else25q->next=p;26q=p;27}28p->next=NULL;29returnhead;30}3132//鏈表的逆置33Node*ReverseList(Node*head){34Node*p,*q,*r;35p=head;36q=r=NULL;37while(p){38q=p->next;39p->next=r;40r=p;41p=q;42}43returnr;44}4546//輸出鏈表47voidShowList(Node*head){48Node*p;49p=head;50while(p){51printf("%d",p->data);52p=p->next;53}54printf("\n");55}5657voidmain(){58Node*head;5960head=CreateList();61printf("鏈表逆置前的數(shù)據(jù):\n");62ShowList(head);6364head=ReverseList(head);65printf("鏈表逆置后的數(shù)據(jù):\n");66ShowList(head);67}運(yùn)行演示：2、判斷單鏈表是否有環(huán)判斷鏈表是否存在環(huán)的辦法為：設(shè)置兩個指針(fast,slow)，初始值都指向頭指針，slow每次前進(jìn)一步，fast每次前進(jìn)兩步，如果鏈表存在環(huán)，則fast必定先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)，兩個指針必定相遇。（當(dāng)然，fast先行從頭到尾部為NULL，則為無環(huán)鏈表）程序如下：1#include<stdio.h>2#include<stdlib.h>34typedefstructnode{5intelem;6structnode*next;7}Node,*NodeList;89boolIsExitsLoop(NodeListhead){10NodeListslow=head,fast=head;11while(fast&&fast->next){12slow=slow->next;13fast=fast->next->next;14if(slow==fast)15break;16}17return!(fast==NULL||fast->next==NULL);18}1920voidmain(){21//創(chuàng)建一個有環(huán)的單鏈表22NodeListhead=NULL,p,q;23for(inti=1;i<=5;i++){24p=(NodeList)malloc(sizeof(Node));25p->elem=i;26if(head==NULL)27head=q=p;28else29q->next=p;30q=p;31}32p=(NodeList)malloc(sizeof(Node));33p->elem=6;34q->next=p;35q=p;36q->next=head->next->next->next;37//判斷單鏈表是否存在環(huán)38printf("單鏈表是否存在環(huán):");39boolb=IsExitsLoop(head);40printf("%s\n",b==false?"false":"true");41}運(yùn)行結(jié)果顯示：3、如果單鏈表有環(huán)，則找到環(huán)的入口點(diǎn)當(dāng)fast若與slow相遇時，slow肯定沒有遍歷完鏈表，而fast已經(jīng)在環(huán)內(nèi)循環(huán)了n圈（1<=n），假設(shè)slow走了s步，而fast走了2s步（fast步數(shù)還等于s加上在環(huán)上多轉(zhuǎn)的n圈），設(shè)環(huán)長為r，則：2s=s+n*r;s=n*r;設(shè)整個鏈表長為L，入口環(huán)與相遇點(diǎn)距離為x，起點(diǎn)到環(huán)入口點(diǎn)的距離為a。a+x=n*r;a+x=(n-1)*r+r=(n-1)*r+L-a;a=(n-1)r+(L–a–x);(L–a–x)為相遇點(diǎn)到環(huán)入口點(diǎn)的距離，由此可知，從鏈表頭到環(huán)入口點(diǎn)等于(n-1)循環(huán)內(nèi)環(huán)+相遇點(diǎn)到環(huán)入口點(diǎn)，于是我們從鏈表頭、與相遇點(diǎn)分別設(shè)一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點(diǎn)為環(huán)入口點(diǎn)。程序描述如下：1#include<stdio.h>2#include<stdlib.h>34typedefstructnode{5intelem;6structnode*next;7}Node,*NodeList;89//尋找環(huán)的入口點(diǎn)10NodeListFindLoopPort(NodeListhead){11NodeListslow=head,fast=head;12while(fast&&fast->next){13slow=slow->next;14fast=fast->next->next;15if(slow==fast)16break;17}18if(fast==NULL||fast->next==NULL)19returnNULL;20slow=head;21while(slow!=fast){22slow=slow->next;23fast=fast->next;24}25returnslow;26}2728voidmain(){29//創(chuàng)建一個有環(huán)的單鏈表30NodeListhead=NULL,p,q;31for(inti=1;i<=5;i++){32p=(NodeList)malloc(sizeof(Node));33p->elem=i;34if(head==NULL)35head=q=p;36else37q->next=p;38q=p;39}40p=(NodeList)malloc(sizeof(Node));41p->elem=6;42q->next=p;43q=p;44q->next=head->next->next->next;45//尋找環(huán)的入口點(diǎn)46NodeListlist=FindLoopPort(head);47printf("環(huán)的入口節(jié)點(diǎn)元素值為：%d\n",list->elem);48}運(yùn)行結(jié)果顯示：4、判斷兩個單鏈表是否相交，如果相交，給出相交的第一個點(diǎn)（兩個鏈表都不存在環(huán)）比較好的方法有兩個：一、將其中一個鏈表首尾相連，檢測另外一個鏈表是否存在環(huán)，如果存在，則兩個鏈表