文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析双指针解法空间复杂度O(1)、时间复杂度O(n)哈希表解法空间复杂度O(n)、时间复杂度O(n)2、解题代码双指针解法空间复杂度O(1)、时间复杂度O(n)哈希表解法空间复杂度O(n)、时间复杂度O(n)三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接234.环形链表2、题目描述二、个人思路整理1、思路分析双指针解法空间复杂度O(1)、时间复杂度O(n)利用快慢指针进行求解快指针每次走两步、慢指针每次走一步如果是非环链表则快、慢指针不可能相遇如果是环形链表则快、慢指针一定会相遇据3来进行判断返回对应结果即可。如果没有环快指针会先到达链表末尾NULL如果有环快指针会先进入环内并一直在里面循环慢指针随后进入环。因为快指针比慢指针每次多走 1 步相对速度为 1快指针一定会追上慢指针两者指向同一个节点。下面是大模型对该解法原理的解释防遗忘在存在环的链表中快慢指针一定会相遇其数学本质是一个追及问题。可以通过以下三个递进的层次来理解相对速度核心原因假设慢指针slow每次走1步快指针fast每次走2步相对速度快指针相对慢指针的速度是2 − 1 1 2 - 1 12−11即快指针每走一步与慢指针的距离就缩短 1 个节点。连续性因为每次距离只减少1 11距离的变小是连续不隔断的从d → d − 1 → d − 2 → ⋯ → 0 d \to d-1 \to d-2 \to \dots \to 0d→d−1→d−2→⋯→0。结论距离必然会减少到0 00也就是两指针重合相遇。对比思考如果快指针每次走 3 步会怎样相对速度变为了3 − 1 2 3 - 1 23−12每次距离缩短2 22。如果进入环时两者的距离是奇数例如 3那么下一次距离变 1再下一次变 -1即直接越过了慢指针变成了K − 1 K-1K−1就会出现套圈/错过的情况需要多跑几圈才能相遇。而相对速度为 1保证了绝不会错失相遇点。数学公式推导设链表头到环入口的距离为a aa环的长度为L LL进入环当slow刚到达环入口时走了a aa步fast已经在环内走了a aa步。初始环内距离此时假设fast领先slow的距离为x xx或者说fast落后slow的距离为L − x L - xL−x。追及过程每次移动fast和slow的距离缩小1 11。经过L − x L - xL−x次移动后距离缩短为0 00。圈数限制因为初始距离小于环长L LL所以慢指针在环里走不完一圈步数 L LL快指针就一定能追上它。这里的“初始距离”指的是慢指针刚进入环的那个瞬间快指针和慢指针在环内的相对距离。 通过简单的逻辑推导就能明白为什么这个距离必然严格小于环长L LL 核心原因 假设环的节点个数环长为L LL。环的节点总数只有L LL个 环内的任意两个节点之间在环内沿着方向数最多只能相距L − 1 L - 1L−1个节点。如果距离达到L LL说明它们绕了一整圈回到了同一个节点距离为 0。慢指针刚进环时快指针已经在环内当慢指针slow刚踩到环的入口节点时它在环内的位置是固定确定的起点。此时快指针fast无论在环内的什么位置它与慢指针的距离只能在0 00到L − 1 L - 1L−1之间。 因此快指针领先慢指针的步数x xx最大也只能是L − 1 L - 1L−1必定满足x L x LxL。 为什么慢指针走不完一圈就会被追上 因为初始距离x L x LxL而快慢指针的追及过程如下快指针相对慢指针的速度是1 11步/次快指针走 2 步慢指针走 1 步相对距离减 1。要消除这x xx的初始距离只需要移动x xx次。每移动 1 次慢指针在环里向前走 1 步。所以从慢指针进入环到被追上慢指针总共只走了x xx步。 因为x L x LxL所以慢指针走的步数x xx一定小于环长L LL。一句话总结环里一共就L LL个位置两人的初始距离最多只有L − 1 L-1L−1。快指针每回合追 1 步所以慢指针最多走L − 1 L-1L−1步还没跑完一圈就会被追上形象的比喻环形跑道想象两人在 400 米的环形跑道上跑步只要两人都在跑且速度不同快的人就一定会对慢的人进行“套圈”。在链表中快指针的速度是慢指针的 2 倍相当于快指针在环里不断套圈慢指针只要在同一个环里重合相遇是必然发生的。哈希表解法空间复杂度O(n)、时间复杂度O(n)遍历链表节点指针类型依次放入哈希表中若在遍历过程中发现已经存在于哈希表中的节点说明存在环若无环则在哈希表中不可能存在相同节点遍历完链表后遍历指针到nullptr结束。根据2中不同情况返回结果即可。2、解题代码双指针解法空间复杂度O(1)、时间复杂度O(n)/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:boolhasCycle(ListNode*head){ListNode*fasthead;ListNode*slowhead;while(fast!nullptrfast-next!nullptr){fastfast-next-next;slowslow-next;//移动后再判断是否追上if(fastslow){//先走再判断否则死循环returntrue;}}returnfalse;}};哈希表解法空间复杂度O(n)、时间复杂度O(n)/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:boolhasCycle(ListNode*head){unordered_setListNode*s;ListNode*phead;while(p!nullptr){if(s.count(p)){returntrue;}s.insert(p);pp-next;}returnfalse;}};三、知识风暴Floyd 判圈算法龟兔赛跑算法利用两个速度不同的指针在环内一定会“套圈重合”的原理来判断链表中是否存在环。核心机制龟兔赛跑慢指针龟 每次走 1 步快指针兔 每次走 2 步。判定依据无环快指针会率先到达链表末尾遇见nullptr有环快慢指针都会进入环内。因为快指针相对慢指针的速度是 1 步/次两者距离每次缩小 1所以快指针一定会追上慢指针并重合不会发生跳过/错过。算法优势时间复杂度O ( N ) O(N)O(N)空间复杂度O ( 1 ) O(1)O(1)极省内存不需要开辟哈希表保存节点。
)
