algorithms►leetcode

014-环形链表（快慢指针）

环形链表

检测链表是否有环（快慢指针法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function hasCycle(head) {
  if (!head || !head.next) return false;
  
  let slow = head;
  let fast = head.next;
  
  while (fast && fast.next) {
    if (slow === fast) return true;
    slow = slow.next;
    fast = fast.next.next;
  }
  
  return false;
}

找到环的起始节点

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
function detectCycleStart(head) {
  if (!head || !head.next) return null;
  
  let slow = head;
  let fast = head;
  let hasCycle = false;
  
  // 检测是否有环
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    
    if (slow === fast) {
      hasCycle = true;
      break;
    }
  }
  
  if (!hasCycle) return null;
  
  // 找到环的起点
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }
  
  return slow;
}

实际应用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 创建环形链表
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // 形成环

// 检测环
console.log('Has cycle:', hasCycle(node1)); // true
console.log('Cycle starts at:', detectCycleStart(node1).data); // 2

环形链表在需要循环访问数据的场景中非常有用，如音乐播放列表、轮播图、资源轮询等。

环形链表检测算法详细解析

这段代码是用来检测链表中是否存在环，并找到环的起始节点的经典算法。它使用了”快慢指针”（Floyd’s Cycle-Finding Algorithm）的方法。下面我将详细解析每一部分的作用和原理。

算法整体思路

  1. 检测是否有环：使用快慢指针遍历链表，如果快指针追上慢指针，则存在环
  2. 找到环的起点：重置一个指针到链表头，然后两个指针同步前进，相遇点即为环的起点

代码逐行解析

第一部分：初始检查

1
if (!head || !head.next) return null;
  • 检查链表是否为空或只有一个节点
  • 这两种情况都不可能形成环，直接返回null

第二部分：初始化指针

1
2
3
let slow = head;
let fast = head;
let hasCycle = false;
  • slow 慢指针，每次前进一步
  • fast 快指针，每次前进两步
  • hasCycle 标记是否检测到环

第三部分：检测环的存在

1
2
3
4
5
6
7
8
9
while (fast && fast.next) {
  slow = slow.next;
  fast = fast.next.next;
  
  if (slow === fast) {
    hasCycle = true;
    break;
  }
}
  • 循环条件：快指针及其下一个节点不为null（防止空指针异常）
  • 慢指针前进一步，快指针前进两步
  • 如果快慢指针相遇，说明存在环，设置标记并退出循环

第四部分：无环处理

1
if (!hasCycle) return null;
  • 如果没有检测到环，直接返回null

第五部分：寻找环的起点

1
2
3
4
5
6
slow = head;
while (slow !== fast) {
  slow = slow.next;
  fast = fast.next;
}
return slow;
  • 将慢指针重置到链表头部
  • 快慢指针现在都每次前进一步
  • 当它们再次相遇时，相遇点就是环的起点
  • 返回这个节点

为什么这个算法有效？

数学原理

设：

  • 链表非环部分长度为 L
  • 环的长度为 C
  • 快慢指针第一次相遇时，慢指针走了 S 步，快指针走了 2S 步

当快慢指针第一次相遇时：

  1. 快指针比慢指针多走了 n 圈环：2S = S + nC ⇒ S = nC
  2. 慢指针走的步数可以表示为：S = L + a（a 是环内位置）

由 L + a = nC ⇒ L = nC - a

这意味着：从链表头到环起点的距离 L，等于从相遇点继续走 nC - a 步。这正是为什么第二次遍历时，从链表头和相遇点同时出发的两个指针会在环起点相遇。

为什么第二次遍历能找到起点？

  1. 第一次相遇后，将慢指针重置到头部
  2. 两个指针现在都每次走一步
  3. 当慢指针走了 L 步到达环起点时：
    • 快指针从相遇点走了 L 步
    • 因为 L = nC - a，所以快指针的位置是：a (原位置) + L = a + nC - a = nC
    • 即快指针也回到了环起点

时间复杂度分析

  • 检测环：O(n) - 最多遍历整个链表一次
  • 寻找起点：O(n) - 最多再遍历一次
  • 总时间复杂度：O(n)

空间复杂度：O(1)，只使用了固定数量的指针

示例演示

考虑链表：1 → 2 → 3 → 4 → 5 → 2（指向节点2形成环）

  1. 第一次遍历：

    • 慢指针路径：1 → 2 → 3 → 4
    • 快指针路径：1 → 3 → 5 → 3 → 5 → …
    • 在节点4相遇

  2. 第二次遍历：

    • 慢指针从头开始：1 → 2
    • 快指针从4开始：4 → 5 → 2
    • 在节点2相遇，这就是环的起点

这个算法巧妙利用了数学关系，通过两次遍历就能准确找到环的起点，是解决环形链表问题的经典方法。