leetcode【每日一题】141. 环形链表 Java【经典放屁题干

    科技2026-10-07  4

    题干

    给定一个链表,判断链表中是否有环。

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

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

    进阶:

    你能用 O(1)(即,常量)内存解决此问题吗?

    示例 1:

    输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。

    示例 2:

    输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。

    示例 3:

    输入:head = [1], pos = -1 输出:false 解释:链表中没有环。

    提示:

    链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个 有效索引 。

    想法

    经典leetcode问题,题干说了tm半天pos,你一看他给的题解的函数,连个pos影子都没见到。

    经典题干再放屁,看函数变量猜他到底要你干啥

    再倒回来看,就是要求链表有没有环嘛 想都不用想,直接上弗洛伊德法,即:龟兔赛跑法

    不熟悉的hxd可以去先了解下哈,简单来说就是如果有环,那么一个一次走一步的🐢一定会被一次两步的🐰追上。

    多说一嘴:怎么判断环的入口:

    先判断有环,记住第一次相遇的节点,从此节点开始遍历,再次遇到此节点中间遍历的长度就是环的长度n,然后两个指针指向头结点,快指针先走n步,然后快慢一起走,相遇的节点即为环入口

    Java代码

    /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head==null||head.next==null){ return false; } ListNode slow=head; ListNode fast=head; while(fast!=null&&fast.next!=null){ slow=slow.next; fast=fast.next.next; if(slow==fast){ return true; } } return false; } }

    我的leetcode代码都已经上传到我的githttps://github.com/ragezor/leetcode

    Processed: 0.021, SQL: 9