LeetCode:141. Linked List Cycle(判断链表中是否有环) 深碍√TFBOYSˉ_ 2022-04-17 05:21 148阅读 0赞 > **文章最前**: 我是Octopus,这个名字来源于我的中文名--章鱼;我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ;这博客是记录我学习的点点滴滴,如果您对 Python、Java、AI、算法有兴趣,可以关注我的动态,一起学习,共同进步。 **相关文章:** 1. **[LeetCode:55. Jump Game(跳远比赛)][LeetCode_55. Jump Game]** 2. **[Leetcode:300. Longest Increasing Subsequence(最大增长序列)][Leetcode_300. Longest Increasing Subsequence]** 3. **[LeetCode:560. Subarray Sum Equals K(找出数组中连续子串和等于k)][LeetCode_560. Subarray Sum Equals K_k]** -------------------- **文章目录:** 题目描述: java实现方法1: Python实现方法1: java实现方法2: Python实现方法2: 源码地址: -------------------- ### 题目描述: ### 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 示例 1: 输入:head = \[3,2,0,-4\], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。 ![format_png][] -------------------- ### java实现方法1: ### /** * 判断链表中是否有环 * * @param head 链表 * @return 布尔值 */ public boolean hasCycle(ListNode head) { Set<ListNode> nodesSeen = new HashSet<>(); while (head != null) { if (nodesSeen.contains(head)) { return true; } else { nodesSeen.add(head); } head = head.next; } return false; } 时间复杂度:O(n) 空间复杂度:O(n) -------------------- ### Python实现方法1: ### def has_cycle_1(self, head: ListNode) -> ListNode: ''' 寻找链表里面的环 Args: head: 头结点 Returns: bool ''' node_set = set() while head: if head in node_set: return True else: node_set.add(head) head = head.next return False 时间复杂度:O(n) 空间复杂度:O(n) -------------------- ### java实现方法2: ### /** * 判断链表中是否有环 * * @param head 链表 * @return 布尔值 */ public boolean hasCycle2(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; } 时间复杂度:O(n) 空间复杂度O(1) -------------------- ### Python实现方法2: ### def has_cycle_2(self, head: ListNode) -> ListNode: ''' 寻找链表里面的环 Args: head: 头结点 Returns: bool ''' if head == None or head.next == None: return False fast = head.next slow = head while slow != fast: if head == None or head.next == None: return False slow = slow.next fast = fast.next.next return True 时间复杂度:O(n) 空间复杂度O(1) -------------------- ### 源码地址: ### [https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode] [github]: https://github.com/zhangyu345293721 [LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870 [Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249 [LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201 [format_png]: /images/20220417/73acaf362e5f442bbf3c42d187674c07.png [https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode
还没有评论,来说两句吧...