leetcode hot100 之【LeetCode 141. 环形链表】 java实现
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 实现解法
方法一:快慢指针
/**
* 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网站