当前位置：首页 > news >正文

025环形链表

news 2026/5/9 12:01:08

环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public boolean hasCycle(ListNode head) { ListNode fast=head, slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow){ return true; } } return false; }

分析：代码的时间复杂度为O(n)，空间复杂度为O(1)。解题思路：快指针和慢指针都从链表起点出发，快指针一次走两步，慢指针一次走一步，若快指针与慢指针能相遇，则链表存在环。

看了官方题解后的解答：

//方法一：哈希表 //时间复杂度：O(n) //空间复杂度：O(n) public boolean hasCycle(ListNode head) { Set<ListNode> set = new HashSet<>(); ListNode cur=head; while(cur!=null){ if(!set.add(cur)){ return true; } cur=cur.next; } return false; } //方法二：快慢指针 //时间复杂度：O(n) //空间复杂度：O(1) public boolean hasCycle(ListNode head) { if(head==null||head.next==null){ return false; } ListNode slow=head, fast=head.next; while(fast!=slow){ if(fast==null||fast.next==null){ return false; } slow=slow.next; fast=fast.next.next; } return true; }

分析：

1、方法一采用哈希表，每次访问到一个元素就看哈希表中是否已经存在，若存在就有环，若不存在就放入哈希表。

2、方法二采用快慢指针，基本原理是Floyd 判圈算法（又称龟兔赛跑算法），快指针一次走两步，慢指针一次走一步，若链表存在环则快慢指针终会相遇（在进入环后，每次移动快指针与慢指针的距离减一）。

3、我的解题思路与官方题解的方法二思路一致，只是实现过程略有不同，官方题解的循环判断条件是快慢指针是否指向同一个位置，所以假设了在head前还存在一个虚拟节点，一开始慢指针从虚拟节点移动一步到head，快指针从虚拟节点移动两步到head.next。而我的思路是在循环内判断快慢指针是否相遇。