「每日LeetCode」2020年10月9日

本文最后更新于：2023年3月19日 晚上

Lt141. 环形链表、142. 环形链表 II，快慢指针

141. 环形链表

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

进阶：
你能用 _O(1)_（即，常量）内存解决此问题吗？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例  2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 10]
  • -10 <= Node.val <= 10
  • pos 为 -1 或者链表中的一个 有效索引 。

思路

使用快慢指针，如果快指针指向的节点和慢指针相同则存在环，若快指针已到链表结尾，不存在环

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  if (!head) return false;
  let fast = head,
    slow = head;
  while (fast) {
    if (fast && fast.next) fast = fast.next.next;
    else break;
    slow = slow.next;
    if (fast === slow) return true;
  }
  return false;
};

142. 环形链表 II（求环形链表的交点）

给定一个链表，返回链表开始入环的第一个节点。  如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。


示例  2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。


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

进阶：
你是否可以不用额外空间解决此题？

思路

使用快慢指针，可以得到以下逻辑：

  1. 慢指针走的路程为：a+c
  2. 快指针走的路程为：两倍慢指针的路程 = a 的长度加 k(k>=1)圈的环加 c 的长度，等价于 2(a+c) = a+kb + c => a+c = kb => a+c = b => b-c = a
  3. 由 b-c = a 可以推出，当相交时让另一个指针指向头结点再走 a 的路程可以刚好达到环形链表的交点。
  4. 可以令慢指针指向头结点，快指针指向不变，两个指针速度相同，等再相遇时，就刚好处于交点处

image.png

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  if (!head) return null;
  let fast = head,
    slow = head;
  while (fast) {
    if (fast && fast.next) fast = fast.next.next;
    else break;
    slow = slow.next;
    if (fast === slow) {
      let slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return fast;
    }
  }
  return null;
};