杏坛网站制作,深圳市商事主体登记注册,12306网站制作,爱站网ip反查域名141.环形链表 1、题目2、题目分析3、解题步骤4、复杂度最优解代码示例5、抽象与扩展 1、题目
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链… 141.环形链表 1、题目2、题目分析3、解题步骤4、复杂度最优解代码示例5、抽象与扩展 1、题目
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 示例 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 105pos 为 -1 或者链表中的一个 有效索引 。 进阶你能用 O(1)即常量内存解决此问题吗 Related Topics 哈希表链表双指针 2、题目分析
关于快慢指针为什么能检测出环可以这么思考。 假设存在一个环: 慢指针进入环后快指针开始追赶慢指针此时快指针距离慢指针为r每一次移动r都会缩小1在经过r次移动后二者就会相遇
如果存在环如何判断环的长度呢方法是快慢指针相遇后继续移动直到第二次相遇。两次相遇间的移动次数即为环的长度。 原因是快慢指针相遇后也意味在新循环里快指针距离慢指针的长度环形链表长度l此时快慢指针每移动一次l缩小1当l缩小为0时快慢指针相遇。而期间移动的次数就是l的长度。
3、解题步骤
1、定义快慢指针为头结点 2、遍历链表直到遍历到了链表尾。fast指针至少跟slow一起到链表尾故是否有链表尾只要判断fast指针即可 3、在快慢指针移动后再比较排除初始都指向头结点的情况。如果有环则链表没有尾所以在这个判断里结束
4、复杂度最优解代码示例 public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {// 遍历链表直到遍历到了链表尾。fast指针至少跟slow一起到链表尾故是否有链表尾只要判断fast指针即可fast fast.next.next;slow slow.next;if (fast slow) {// 在指针移动后再比较排除初始都指向头结点的情况。如果有环则链表没有尾所以在这个判断里结束return true;}}return false;}5、抽象与扩展
环形链表的使用场景 环形缓冲区在数据处理中环形缓冲区是一个重要的概念。环形缓冲区使用环形链表来实现当缓冲区满时新的数据会覆盖旧的数据。
