题目地址(142. 环形链表 II)

https://leetcode-cn.com/problems/linked-list-cycle-ii/

题目描述

  1. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
  3. 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
  5. 说明：不允许修改给定的链表。
  7. 进阶：
  9. 你是否可以使用 O(1) 空间解决此题？
  13. 示例 1：
  15. 输入：head = [3,2,0,-4], pos = 1
  16. 输出：返回索引为 1 的链表节点
  17. 解释：链表中有一个环，其尾部连接到第二个节点。
  20. 示例 2：
  22. 输入：head = [1,2], pos = 0
  23. 输出：返回索引为 0 的链表节点
  24. 解释：链表中有一个环，其尾部连接到第一个节点。
  27. 示例 3：
  29. 输入：head = [1], pos = -1
  30. 输出：返回 null
  31. 解释：链表中没有环。
  36. 提示：
  38. 链表中节点的数目范围在范围 [0, 104] 内
  39. -105 <= Node.val <= 105
  40. pos 的值为 -1 或者链表中的一个有效索引

前置知识

  • 哈希表

公司

  • 暂无

思路

遍历循环中的每一个节点 判断节点是否在set中 没遍历过的节点add到set 遍历过的节点证明链表有环 并且是环的入口

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for singly-linked list.
  4.  * class ListNode {
  5.  *     int val;
  6.  *     ListNode next;
  7.  *     ListNode(int x) {
  8.  *         val = x;
  9.  *         next = null;
  10.  *     }
  11.  * }
  12.  */
  13. public class Solution {
  14.         public ListNode detectCycle(ListNode head) {
  15.             ListNode pos = head;
  16.             HashSet<ListNode> listNodes = new HashSet<>();
  17.             while (pos != null) {
  18.                 if (listNodes.contains(pos)) {
  19.                     return pos;
  20.                 } else {
  21.                     listNodes.add(pos);
  22.                 }
  23.                 pos = pos.next;
  24.             }
  25.             return null;
  26.         }
  27.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：142. 环形链表 II (2) - 图1#card=math&code=O%28n%29&id=btx87)
  • 空间复杂度：142. 环形链表 II (2) - 图2#card=math&code=O%28n%29&id=GXuY1)