大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个链表的头节点,判断链表中是否有环。”
2、题目描述
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
示例 1: 输入: head = [3,2,0,-4], pos = 1 输出: true 解释: 链表中有一个环,其尾部连接到第二个节点。
示例 2: 输入: head = [1,2], pos = 0 输出: true 解释: 链表中有一个环,其尾部连接到第一个节点。
二、解题
1、思路分析
这道题可以遍历所有节点,然后遍历到一个节点后,判断该节点是否被访问过。
记录节点是否被访问过,可以使用哈希表,每次到达一个节点,如果节点存在于哈希表,则说明该链表是环形链表。
否则,就将该节点加入到哈希表中,重复这一过程,直到遍历完整个链表。
2、代码实现
代码参考:
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; } }
3、时间复杂度
时间复杂度:O(N)
其中N是链表中的节点数。
空间复杂度:O(N)
其中N是链表中的节点数,空间的开销主要是哈希表的开销,最坏的情况下需要将每个节点都插入到哈希表一次。
三、总结
这道题还可以使用双指针,用快慢指针,快指针每次走两步,慢指针每次走一步。 当快指针追上慢指针则表示有环。
如果快指针指向null,这说明链表没环。