摄影作品发布平台_有名的外贸公司_如何做好网站的推广工作_专业排名优化工具

• 你好，我是杨十一，一名热爱健身的程序员
• 在Coding的征程中，不断探索与成长
• LeetCode热题100——刷题记录（不定期更新）
  此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
  愿与诸君共同探讨，在代码世界里携手共进，攻克难题，提升自我

题目描述

给定一个链表的头节点head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。
注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。示例 1：输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。

提示：链表中节点的数目范围在范围 [0, 104] 内-105 <= Node.val <= 105pos 的值为 -1 或者链表中的一个有效索引进阶：你是否可以使用 O(1) 空间解决此题？

代码实现

• 思路一：哈希表

public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> set = new HashSet<>();ListNode node = head;while (node != null) {if (set.contains(node)) {return node;} else {set.add(node);}node = node.next;}return null;}
}

• 思路二：快慢指针

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (fast == slow) {ListNode node = head;while (node != slow) {node = node.next;slow = slow.next;}return node;}}return null;}
}

• 数据结构

class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}
}

思路解析

1. 输入：链表头节点 ListNode head
2. 输出：链表成环节点 ListNode cycleNode 无环则返回 null
3. 思路一：哈希表 HashSet
   • 关键：尾节点的 next 指向
     • 无环，next == null
     • 有环，next -> node 链表中某个节点
     • 有环，遍历链表，当某个节点被第二次访问到时，它就是尾节点的next
   • 时间复杂度：$O(n)$
   • 空间复杂度：$O(n)$
4. 思路二：快慢指针
   • 慢指针slow一次移动1个位置，快指针fast一次移动2个位置
     • 无环，fast 指针将先走到尾节点或尾节点的前一个节点，其后 next == null
     • 有环，快指针将追上慢指针，二者相遇
   • 关键节点：入环节点 C & 相遇节点 M
   • 关键思路：快慢指针相遇后到入环节点的距离等于头节点到入环节点的距离

• 推理逻辑：
  • 设定参数
    • L ：头节点到入环节点的距离
    • T ：入环节点到相遇节点的距离
    • R ：相遇节点到入环节点的距离
  • 当快慢指针相遇时
    • 慢指针移动距离：L + T
    • 快指针移动距离：L + q * (T + R) + T
      • 其中 q*(T+R)代表快指针先经过入环节点并已走完 q 圈 (q = 1,2,3,...)
    • 同时，快指针移动距离 = 慢指针的两倍，即 L + q * (T + R) + T = 2 * (L + T)
    • 化简公式：(q - 1) * (T + R) + R = L 可推理出 R = L
    • 等式左侧：从相遇节点 M 起走到入环节点 C （经过 q-1圈）
    • 等式右侧：从头节点 head 起走到入环节点 C
• 时间复杂度：$O(n)$ = $O(n)+O(n)$
  • 虽然是双循环嵌套，但满足条件的内层循环只执行1次
  • 外层循环寻找相遇节点，慢指针移动不超过 n 次，寻找过程不触发内层循环执行
  • 内层循环寻找入环节点，指针移动不超过 n 次，相遇后内层循环执行完直接return
• 空间复杂度：$O(1)$ 只用了3个指针

5. 相关知识点

---

• 你好，我是杨十一，一名热爱健身的程序员
• 在Coding的征程中，不断探索与成长
• LeetCode热题100——刷题记录（不定期更新）
  此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
  愿与诸君共同探讨，在代码世界里携手共进，攻克难题，提升自我