LeetCode 141. 环形链表 题目描述题目级别简单给你一个链表的头节点head判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。如果链表中存在环 则返回true。 否则返回false。 解法一哈希表备忘录判断是否“绕圈子”最符合人类直觉的思维方式就是“记事本法”。我们在遍历链表的过程中把路过的每一个节点的内存地址都记在小本本哈希表上。每次往前走一步都先查一下本子如果这个地址本子上没有就把它记下来继续往下走。如果走到某个节点发现它的地址竟然已经在本子上了这说明我们回到了曾经来过的地方必定有环。如果一路走到nullptr都没有重复说明链表是一条直到尽头的直线没有环。 C 代码实现 (哈希表法)classSolution{public:boolhasCycle(ListNode*head){// 使用 unordered_set 记录访问过的节点指针unordered_setListNode*seen;while(head!nullptr){// 如果在集合中找到了当前节点说明绕回来了if(seen.count(head))returntrue;// 没找到就把它加入集合留下访问记录seen.insert(head);// 继续往下走headhead-next;}// 走到尽头了说明没环returnfalse;}}; 解法二Floyd 快慢指针 (龟兔赛跑)为了彻底消灭哈希表带来的空间消耗我们可以引入两个不同速度的指针慢指针 (slow)每次只走 1 步。快指针 (fast)每次走 2 步。这就是著名的“龟兔赛跑”算法。情况 1没有环。快指针跑得快它或者它的下一步会率先到达跑道的尽头nullptr。比赛直接结束判定无环。情况 2有环。这就非常有意思了。快指针会率先进入环内并在环里无休止地打转。当慢指针也进入环内时这场赛跑就变成了操场上的追击战。因为快指针每次比慢指针多走一步所以无论两人的初始距离多远快指针最终一定会以每次缩短 1 步的进度从后面稳稳地“追上”重合慢指针只要两个指针重合了就说明一定存在环 C 代码实现 (快慢指针法)classSolution{public:boolhasCycle(ListNode*head){// 空链表或只有一个节点的链表肯定无环if(headnullptr||head-nextnullptr)returnfalse;ListNode*slowhead;ListNode*fasthead-next;// 只要没相遇比赛就继续while(slow!fast){// 如果快指针走到尽头说明跑道是直的无环if(fastnullptr||fast-nextnullptr){returnfalse;}// 慢指针走一步slowslow-next;// 快指针走两步fastfast-next-next;}// 循环被打破说明 slow fast套圈相遇了有环returntrue;}};