142. 环形链表 II

难度: 中等

来源: 每日一题 2023.07.30

---

给定一个链表的头节点  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, 10^4]
• -10^5 <= Node.val <= 10^5
• pos 为 -1 或者链表中的一个 有效索引 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode detectCycle(ListNode head) {

    }
}

分析与题解

---

• 缓存暴力法

  一个链表是否有环, 在昨天已经实现了, 我们是利用了两个快慢指针来判别是否有环, 当我们需要判别环的起始点时, 我们可以利用缓存存储我们遍历过的点, 当点再次出现的时候就是我们需要的题解.

  • 首先,需要做结果的边界处理.

    if (head == null) {
        return null;
    }
    

  • 然后就是遍历, 并且查找起始点.

    Set<ListNode> cache = new HashSet<ListNode>();
    ListNode result = null;
    while(head != null) {
        if (cache.contains(head)) {
            result = head;
            break;
        }
        cache.add(head);
        head = head.next;
    }
    

  整个解题过程如下所示.

  /**
  * Definition for singly-linked list.
  * class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) {
  *         val = x;
  *         next = null;
  *     }
  * }
  */
  public class Solution {
      public ListNode detectCycle(ListNode head) {
          if (head == null) {
              return null;
          }
          Set<ListNode> cache = new HashSet<ListNode>();
          ListNode result = null;
          while(head != null) {
              if (cache.contains(head)) {
                  result = head;
                  break;
              }
              cache.add(head);
              head = head.next;
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

  结果如下所示.