环形链表1在介绍环形表时我们主要以题目的形式进行讲解呈现。题目链接https://leetcode.cn/problems/linked-list-cycle/对于这个题思路为快慢指针让快指针走两步慢指针走一步如果两指针相遇则说明该链表带环。具体实现如下#includestdio.h #includestdbool.h typedef int SLDataType; typedef struct ListNode { SLDataType x; struct ListNode* next; }ListNode; bool hasCycle(ListNode* head) { ListNode* fast head; ListNode* slow head; while (fastfast-next) { //慢指针走一步快指针走两步 slow slow-next; fast fast-next-next; if (fast slow)//快慢指针相遇 { return true; } } //两指针始终没有相遇即不存在环 return false; }但问题是为什么快慢指针相遇就会带环如何证明以及如果快指针如果走3步、4步......呢证明推理如下如果链表当中存在环快指针一次走两步慢指针一次走一步那么在慢指针即将入环前快指针已经入环且两者此刻相距为N且两者走一步距离就-1所以fast与slow距离变化为N,N-1,N-2,N-3......1,0。所以如果存在环快指针走两步慢指针走一步两者会相遇。但如果走3、4、5......呢如果慢指针走1步快指针走3步两者步差为2当slow即将入环的一刻假设fast与slow之间距离为N。①当N为偶数时快慢指针相距的距离为N,N-2,N-4,N-6......2,0(相遇)。②当N为奇数时快慢指针相距的距离为N,N-2,N-4,N-6......3,1,-1(错过)。假设环的周长为C当错过时快指针追慢指针两者相距的距离为C-1。当C-1为偶数时第二圈会相遇(①中已说明)。当C-1为奇数时不会相遇会一直错过②中已说明所以总结出来限制条件N为奇数C-1为奇数即C为偶数快慢指针不会相遇。那么这个结论到底对不对呢假设环的周长为C所以快指针走过的路程为fastLxC(走过的圈数)C-N(快慢指针相距的距离)slowL。又因为快指针一次走三步慢指针一次走一步所以3slow fast代入得3L LxCC-N,所以2L xCC-NC(c1)-N。2L肯定为偶数所以xCC-N为偶数那么就有这两种可能①偶数-偶数 偶数②奇数-奇数 偶数排除①因为限制结论为N为奇数C为偶数。那么看②则C(x1)为奇数,又因为x为跑了多少圈对过程分析影响不大所以可以忽略因此这里得出C为奇数显然与之前得出得结论不符所以N为奇数C为偶数不存在即不管怎么快慢指针始终相遇。同理快指针走4、5、6......证明同上。环形链表2题目链接https://leetcode.cn/problems/linked-list-cycle-ii/description/对于环形表2思路同样为快慢指针不过还需要一个指向头节点的指针当快慢指针相遇时让指向头节点的指针与相遇点指针步频为都走一步指向头节点指针与快慢指针相遇点指针再次相遇的地方为入环节点。#define _CRT_SECURE_NO_WARNINGS 1 #includestdio.h typedef int SLDataType; typedef struct ListNode { SLDataType x; struct ListNode* next; }ListNode; ListNode* FindMidNode(ListNode* head) { ListNode* fast head; ListNode* slow head; while (fast fast-next) { //慢指针走一步快指针走两步 slow slow-next; fast fast-next-next; if (fast slow)//快慢指针相遇 { return slow; } } } ListNode* DetectCycle(ListNode* head) { //找相遇点 ListNode* meet FindMidNode(head); //相遇点与头节点相遇的位置即为入环位置 ListNode* pcur head; while (meet pcur) { if (pcur meet)//可能头尾相连并且相遇点在头节点所以先判断 { return meet; } meet meet-next; pcur pcur-next; } //链表不带环 return NULL; }证明过程如下假设相遇点M为MeetE为入环节点L为指向头节点you的指针到入环节点的距离E到M距离为X原周长为Rslow指针走的距离为LX,fast指针走的距离为LXnR又因为fast 2*slow所以LXnR 2*(LX)所以L nR-X即L (n-1)R(R-X)。又因为n最小取1(在slow入环前fast就已经走到了M点当后续又在M点相遇fast最少走了一圈所以n取值为1、2、3、4、5、6......),(n-1)R为圈数对逻辑推理影响不大取n 1所以L R-X。所以指向头节点的指针与Meet指针各走一步会在入环位置相遇。
