1.判断单链表是否有环
使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。
就是所谓的追击相遇问题：
代码示例如下：
//判断链表是否有环，如果无环返回NULLListNode* HasCircle(LinkList head){if(head==NULL)return NULL;ListNode *slow=head;ListNode *fast=head;while(fast!=NULL){slow=slow->next;//走一步fast=fast->next;if(fast!=NULL)fast=fast->next;elsereturn NULL;//如果slow==fast，则有环if(slow==fast)return slow;}//while条件为假，则退出循环return NULL;}
2.求有环单链表的环连接点位置
第一次碰撞点Pos到连接点Join的距离=头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。
在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。
第一次相遇时，slow走的长度 S =LenA+x;
第一次相遇时，fast走的长度 2S =LenA+ n*R+x;
所以可以知道，LenA+x =n*R; LenA = n*R -x;
代码示例如下：
//判断一个链表是否有环，如果有,返回环的入口点；如果无环，则返回NULLListNode* CircleEntrance(LinkList head){if(head==NULL)return NULL;ListNode *slow=head;ListNode *fast=head;while(fast!=NULL){slow=slow->next;//走一步fast=fast->next;if(fast!=NULL)fast=fast->next;elsereturn NULL;//如果slow==fast，则有环if(slow==fast)break;}//while条件为假，则退出循环if(fast==NULL)//无环退出return NULL;else{//求入口点位置slow=head;while(slow!=fast){slow=slow->next;fast=fast->next;}return slow;}}
3.求有环单链表的环长
已知环的起点，很容易求环的长度。
示例代码如下：
//如果一个链表有环，返回环的长度；无环，则返回0int CircleLength(LinkList head){if(head==NULL)return 0;ListNode *slow=head;ListNode *fast=head;while(fast!=NULL){slow=slow->next;//走一步fast=fast->next;if(fast!=NULL)fast=fast->next;elsereturn 0;//如果slow==fast，则有环if(slow==fast)break;}//while条件为假，则退出循环if(fast==NULL)//无环退出return 0;else{slow=head;while(slow!=fast){slow=slow->next;fast=fast->next;}//while()slow指向int circlelen=1;ListNode *p=slow;//求环的长度while(p->next!=slow){++circlelen;p=p->next;}return circlelen;}}
4.求有环单链表的链表长
上述3中求出了环的长度；2中求出了连接点的位置，就可以求出头结点到连接点的长度。两者相加就是链表的长度。
5.尾插法建立链表
typedef struct ListNode{int data;struct ListNode* next;}ListNode,*LinkList;//尾插法创建带环的链表LinkList CreateLinkList(){LinkList head=NULL;ListNode *pre=NULL,*inter=NULL;//尾插法建立链表for(int i=1;i<=6;i++){//创建结点ListNode *temp=(ListNode*)malloc(sizeof(ListNode));temp->data=i;temp->next=NULL;if(head==NULL){head=temp;pre=head;}else{pre->next=temp;pre=temp;//尾插法}if(i==6)inter=temp;//i==3值处为交叉点}pre->next=inter;//建立链表的环return head;}
6.测试代码
int main(){LinkList head=CreateLinkList();int circlelen=CircleLength(head);if(!circlelen)cout<<"no circle"<<endl;else{cout<<"has circle"<<endl;cout<<"circle entrance is "<<circlelen<<endl;}return 0;}
肯承认错误则错已改了一半
