【每天学习一点算法 2025/12/15】环形链表

每天学习一点算法 2025/12/15

题目：环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

1. 首先想到的方法就是用Map存储节点，如果遇到重复的节点说明有环。

   functionhasCycle(head:ListNode|null):boolean{if(!head||!head.next)returnfalse;constmap=newMap();while(head){if(map.has(head.next))returntrue;map.set(head,head.val);head=head.next;}returnfalse;};

2. 「Floyd 判圈算法」（又称龟兔赛跑算法）、

   Floyd 判圈算法（Floyd’s Tortoise and Hare Algorithm）是一种空间复杂度为 O (1)的算法，用于检测链表、迭代序列等结构中是否存在环，并能找到环的入口点，核心思想是通过快慢指针的移动规律来判断环的存在。

   • 定义两个指针：慢指针（龟）每次移动 1 步，快指针（兔）每次移动 2 步。
   • 若结构中无环：快指针会先到达终点（如链表的null）。
   • 若结构中有环：快慢指针最终会在环内某个节点相遇（因为快指针在环内 “追赶” 慢指针，且步长差为 1，必然会追上）。

   functionhasCycle(head:ListNode|null):boolean{if(!head||!head.next)returnfalse;letslow:ListNode|null=head;letfast:ListNode|null=head.next;while(slow!==fast){if(!fast||!fast.next)returnfalse;slow=slow?.next||null;fast=fast.next.next;}returntrue;}

题目来源：力扣（LeetCode）