LeetCode热题100（二十六） —— 142.环形链表II

• 你好，我是杨十一，一名热爱健身的步伐员
  
• 在Coding的征程中，不停探索与发展
  
• LeetCode热题100——刷题记载（不定期更新）
  此系列文章用于记载我在学习 LeetCode热题100 过程中的总结和劳绩
  愿与诸君共同探究，在代码天下里携手共进，攻克困难，提升自我
  

标题形貌

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

复制代码

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

复制代码

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

复制代码

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

复制代码

代码实现

• 思绪一：哈希表
  

1. public class Solution {
2.     public ListNode detectCycle(ListNode head) {
3.         Set<ListNode> set = new HashSet<>();
4.         ListNode node = head;
5.         while (node != null) {
6.             if (set.contains(node)) {
7.                 return node;
8.             } else {
9.                 set.add(node);
10.             }
11.             node = node.next;
12.         }
13.         return null;
14.     }
15. }

复制代码

• 思绪二：快慢指针
  

1. public class Solution {
2.     public ListNode detectCycle(ListNode head) {
3.         ListNode fast = head;
4.         ListNode slow = head;
5.         while (fast != null && fast.next != null) {
6.             slow = slow.next;
7.             fast = fast.next.next;
8.             if (fast == slow) {
9.                 ListNode node = head;
10.                 while (node != slow) {
11.                     node = node.next;
12.                     slow = slow.next;
13.                 }
14.                 return node;
15.             }
16.         }
17.         return null;
18.     }
19. }

复制代码

• 数据结构
  

1. class ListNode {
2.         int val;
3.         ListNode next;
4.         ListNode(int x) {
5.                 val = x;
6.                 next = null;
7.         }
8. }

复制代码

思绪剖析

• 输入：链表头节点 ListNode head
  
• 输出：链表成环节点 ListNode cycleNode 无环则返回 null
  
• 思绪一：哈希表 HashSet
  
  
  
  • 关键：尾节点的 next 指向
    
    
    
    • 无环，next == null
      
    • 有环，next -> node 链表中某个节点
      
    • 有环，遍历链表，当某个节点被第二次访问到时，它就是尾节点的next
      
    
    
  • 时间复杂度：                                             O                               (                               n                               )                                      O(n)                        O(n)
    
  • 空间复杂度：                                             O                               (                               n                               )                                      O(n)                        O(n)
    
  
  
• 思绪二：快慢指针
  
  
  
  • 慢指针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) =                                    O                         (                         n                         )                         +                         O                         (                         n                         )                              O(n)+O(n)                  O(n)+O(n)
  
  
  
  • 固然是双循环嵌套，但满足条件的内层循环只实行1次
    
  • 外层循环探求相遇节点，慢指针移动不高出 n 次，探求过程不触发内层循环实行
    
  • 内层循环探求入环节点，指针移动不高出 n 次，相遇后内层循环实行完直接return
    
  
  
• 空间复杂度：                                   O                         (                         1                         )                              O(1)                  O(1) 只用了3个指针
  

• 干系知识点
  

---

• 你好，我是杨十一，一名热爱健身的步伐员
  
• 在Coding的征程中，不停探索与发展
  
• LeetCode热题100——刷题记载（不定期更新）
  此系列文章用于记载我在学习 LeetCode热题100 过程中的总结和劳绩
  愿与诸君共同探究，在代码天下里携手共进，攻克困难，提升自我
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。