科技公司网页设计欣赏,网站优化 seo和sem,建设教育局网站硬件价格需要多少钱?,设计制作活动内容的原则目录 题目描述#xff1a;141. 环形链表#xff08;简单#xff09;题目接口解题思路代码 PS: 题目描述#xff1a;141. 环形链表#xff08;简单#xff09;
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连… 目录 题目描述141. 环形链表简单题目接口解题思路代码 PS: 题目描述141. 环形链表简单
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
LeetCode做题链接LeetCode-环形链表
示例 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 或者链表中的一个 有效索引 。进阶 你能用 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) {}
}解题思路
参考思路相爱相杀的好基友-数组与链表 里面讲解了获取倒数第k个元素获取中间位置的元素判断链表是否存在环判断环的长度讲的很好而且有图解 这题主要是用到了快慢指针的方法只要里面又换快慢指针在环内总会相遇如果没环快指针的next或者快指针的next.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 slow head;ListNode fast head.next;// 若是环最终会在环内相遇while (slow ! fast) {// 若不是环形链表最终会等于空if (fast null || fast.next null) {return false;}// 快慢指针的移动slow slow.next;fast fast.next.next;}return true;}
}扩展 如果存在环如何判断环的长度呢 方法是快慢指针相遇后继续移动直到第二次相遇。两次相遇间的移动次数即为环的长度。 成功
PS:
感谢您的阅读如果您觉得本篇文章对您有所帮助请给予博主一个赞喔~
