“给定一个链表的头节点,判断链表中是否有环。”
题目链接:
来源:力扣(LeetCode)
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
示例 1:
输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入: head = [1,2], pos = 0
输出: true
解释: 链表中有一个环,其尾部连接到第一个节点。
这道题可以遍历所有节点,然后遍历到一个节点后,判断该节点是否被访问过。
记录节点是否被访问过,可以使用哈希表,每次到达一个节点,如果节点存在于哈希表,则说明该链表是环形链表。
否则,就将该节点加入到哈希表中,重复这一过程,直到遍历完整个链表。
代码参考:
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是链表中的节点数,空间的开销主要是哈希表的开销,最坏的情况下需要将每个节点都插入到哈希表一次。
这道题还可以使用双指针,用快慢指针,快指针每次走两步,慢指针每次走一步。 当快指针追上慢指针则表示有环。
如果快指针指向null,这说明链表没环。