LeetCode:142. Linked List Cycle II(找出链表中的环) 分手后的思念是犯贱 2022-04-05 09:10 103阅读 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][)][Leetcode_300. Longest Increasing Subsequence]** -------------------- **文章目录:** 题目描述: java实现方法1: python实现方式1: 源码github地址:https://github.com/zhangyu345293721/leetcode -------------------- ### 题目描述: ### 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 说明:不允许修改给定的链表。 -------------------- 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail connects to node index 1 解释:链表中有一个环,其尾部连接到第二个节点。 示例 2: 输入:head = [1,2], pos = 0 输出:tail connects to node index 0 解释:链表中有一个环,其尾部连接到第一个节点。 来源:力扣(LeetCode) -------------------- ### java实现方法1: ### /** * 找出链表中的环 * * @param head 头指针 * @return 环对象 */ public ListNode detectCycle(ListNode head) { if (head == null) { return null; } ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (fast == null) { return null; } if (slow == fast) { break; } } if (fast == null || fast.next == null) { return null; } slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } 时间复杂度:O(n) 空间复杂度:O(1) -------------------- ### python实现方式1: ### class ListNode: def __init__(self, val, next): self.val = val self.next = next def get_detect_cycle(head): ''' 头结点 Args: head: 头结点位置 Returns: 环中头结点位置 ''' if len(head) < 1: return None slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if fast == None: return None if slow == fast: break if not fast or not fast.next : return None slow = head while slow != fast: slow = slow.next fast = fast.next return slow 时间复杂度:O(n) 空间复杂度:O(1) -------------------- ### 源码github地址: ### [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 [https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode
还没有评论,来说两句吧...