LeetCode中环形链表题解-java
题目
141. 环形链表
难度简单877收藏分享切换为英文接收动态反馈
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 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
或者链表中的一个 有效索引 。
题解
方法一:双指针-快慢指针
思路
定义两个指针,为快慢指针,慢指针一开始位于head,快指针位于head .next ,慢指针一次移动一步,快指针一次移动两步, 如果,在移动的过程中,快慢指针重合,说明该链表为环形链表,否则快指针到达链表尾部,该链表不为环形链表
代码实现
/**
* 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) {
// 如果head为空,或者head.next为空,返回false
if (head == null || head.next == null) {
return false;
}
// 定义一个慢指针与快指针
ListNode slow = head;
ListNode fast = head.next;
// 如果快慢指针不相同,进入循环
while(slow != fast ){
// 如果快指针为空或,快指针的下一指针为空,则返回false
if(fast == null || fast.next == null){
return false;
// 如果不为空,则慢指针走一步,快指针走两步,进入下一循环判断
}else{
slow = slow.next;
fast = fast.next.next;
}
}
return true;
}
}
复杂度分析
- 时间复杂度:O(N),其中 N 是链表中的节点数。
- 空间复杂度:O(1)。我们只使用了两个指针的额外空间。
提交详情
方法二:哈希表
思路
遍历所有节点,每次遍历一个节点时,判断是否存在哈希表中,如果存在说明为环形链表,若不存在,则将该节点加入到哈希表中,重复这一过程,直到遍历结束
代码实现
/**
* 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) {
Set<ListNode> seen = new HashSet<ListNode>();
while (head != null) {
if (!seen.add(head)) {
return true;
}
head = head.next;
}
return false;
}
}
复杂度分析
- 时间复杂度:O(N),其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。
- 空间复杂度:O(N),其中 N 是链表中的节点数。主要为哈希表的开销,最坏情况下我们需要将每个节点插入到哈希表中一次。