LeetCode 141. 环形链表

题目描述

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（pos 索引从 0 开始）。如果 pos 为 -1，则表示链表中没有环。

示例 1：

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

示例 2：

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

示例 3：

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

Java 实现解法

方法一：快慢指针

java">/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*//*** 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 fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {return true;}}return false;}
}

解题思路

• 快慢指针法：这是一种非常经典的判断链表中是否有环的方法，也称为 Floyd 算法。
  • 我们初始化两个指针 slow 和 fast，分别指向链表的头节点。
  • slow 每次移动一步，fast 每次移动两步。
  • 如果链表中有环，那么 fast 指针最终会追上 slow 指针，因为 fast 的移动速度是 slow 的两倍。
  • 如果链表中没有环，fast 指针会先到达链表的末尾，即 fast 或 fast.next 将为 null，此时函数返回 false。

这种方法的时间复杂度是 O(n)，其中 n 是链表的长度。空间复杂度是 O(1)，因为我们只使用了有限的额外空间来存储指针。这种方法简单且高效，是检测链表中环的首选方法。

注：来源leetcode网站