环形链表1
运用快慢指针的方法，fast ,slow从头节点出发，快指针走两步，慢指针走一步，若有环，快指针先进环，后续如果慢指针和快指针相遇，则链表带环。转换成了追击问题。
struct ListNode { int val; struct ListNode *next; }; typedef struct ListNode LN; bool hasCycle(struct ListNode *head) { LN*slow,*fast; slow=fast=head; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; if(slow==fast) return true; } return false; }
思考：为什么一定会相遇，会不会错过，永远追不上？若快指针走三步，四步呢？
证明：假设链表就是有环，slow（1步）进环时，fast（两步）与slow的距离为N,追击过程中，每走一次，N都会-1，最后到0。本题的思想证明，距离为0就是追上了。
若fast走三步，同样假设slow进环时，fast与slow相差N,
fast追击slow过程中，距离变化一直-2,但是最后结果要注意，N为偶数时，最后变为0，N为奇数时，最后为-1.而当距离为-1时，两指针会错过，进行新一轮追击。这时假设环的长度为C。新的距离就变成C-1了，这是又要将C分为奇数，偶数进行讨论。
那么是否存在N是奇数且C是偶数的情况呢，
假设从出发位置到进环的位置相差L，slow进环时，fast已经走了x圈，且fast与slow相差N:
进环时：slow走的距离->L
fast走的距离->L+x*C+C-N
fast的距离应该为slow的三倍:3*L=L+x*C+C-N
化简为：2*L=(x+1)*C-N 若要满足该等式，若C是偶数,N必须是偶数。若N是奇数,如果C是偶数，则（x+1）*偶数一定是偶数，偶数-奇数！=偶数。
所以上述条件不成立，故永远追不上的条件不成立。
结论：一定能追上。
N是偶数第一轮追上。N是奇数第一轮追不上，C是奇数，第二轮追上。
其他走四步等的条件证明过程类似。
环形链表2
本题相较于第一个环形链表题，多了返回节点位置的步骤，所以最初思路也是通过快慢指针，快慢指针相遇，则证明有环存在，然后将两指针相遇点记为meet，再继续走，此时头节点也开始移动，meet与head相遇点就是环的最初节点。
证明过程如下：
struct ListNode { int val; struct ListNode *next; }; typedef struct ListNode LN; struct ListNode *detectCycle(struct ListNode *head) { LN*slow,*fast,*meet; slow=fast=head; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; if(slow==fast){ meet=slow; while(meet!=head){ meet=meet->next; head=head->next; } return meet; } } return NULL; }
这种方法不容易想到，还有另外一种方法，将快慢指针相遇点newhead=meet->next,meet->next=NULL,此时从newhead开始，与原链表head通过相交链表的思路求解。
struct ListNode { int val; struct ListNode *next; }; typedef struct ListNode LN; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { LN*cur1=headA,*cur2=headB; int lenA=1,lenB=1; while(cur1){ cur1=cur1->next; lenA++; } while(cur2){ cur2=cur2->next; lenB++; } //尾节点不相同就没有相交 if(cur1!=cur2){ return NULL; } //假设法 int gap=abs(lenA-lenB); LN* longlist = headA; LN* shortlist = headB; if(lenA<lenB){ longlist=headB; shortlist=headA; } while(gap--){ longlist=longlist->next; } while(longlist!=shortlist){ longlist=longlist->next; shortlist=shortlist->next; } return longlist; } struct ListNode *detectCycle(struct ListNode *head) { LN*slow,*fast,*meet; slow=fast=head; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; if(slow==fast){ meet=slow; LN* newhead=meet->next; meet->next=NULL; return getIntersectionNode(head,newhead); } } return NULL; }
本节内容到此结束，感谢各位友友对小编的支持！！！
觉得本文章有用的话留下三连和评论吧！！！
咱们下期再见！！！
