跳到主要内容

142. 环形链表 II

题目描述​

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

出处：LeetCode

解法一：哈希表​

思路​

我们可以使用哈希表来判断链表中是否有环。我们定义一个哈希表 set，然后遍历链表，每次遍历时，我们判断当前节点是否在哈希表中，如果在，则说明链表中有环，返回当前节点；否则，我们将当前节点加入哈希表中。当遍历结束后，说明链表中没有环，返回 null。

实现​

function detectCycle(head: ListNode | null): ListNode | null {
  const set = new Set<ListNode>();

  while (head !== null) {
    if (set.has(head)) {
      return head;
    }

    set.add(head);
    head = head.next;
  }

  return null;
}

复杂度分析​

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

解法二：快慢指针​

思路​

我们可以使用快慢指针来判断链表中是否有环。我们定义两个指针 slow 和 fast，分别指向链表的头节点 head。然后我们遍历链表，每次迭代时，slow 指针向后移动一个节点，fast 指针向后移动两个节点。如果链表中有环，那么 slow 和 fast 指针一定会在环中相遇。当 slow 和 fast 指针相遇时，我们将 fast 指针重新指向链表的头节点 head，然后 slow 和 fast 指针同时向后移动一个节点，直到 slow 和 fast 指针再次相遇。此时，slow 和 fast 指针相遇的节点就是链表开始入环的第一个节点。

实现​

function detectCycle(head: ListNode | null): ListNode | null {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;

    if (slow === fast) {
      fast = head;

      while (slow !== fast) {
        slow = slow!.next;
        fast = fast!.next;
      }

      return slow;
    }
  }

  return null;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)