📓 Archive

CYCLE-LINKED

FGJ: Create:2025/01/19 Update: (2025-01-20)

  • Intro(CYCLE-LINKED | 环形链表检测) #

    • 题目描述 #

      给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。如下：

      graph LR; A[3] --> B[2]; B --> C[0]; C --> D[-4]; D --> B; style B fill:#6f9,stroke:#333,stroke-width:4px;
      graph LR; A[3] --> B[2]; B --> C[0]; C --> D[-4]; D --> E[NULL];

      Attention

      在力扣题目 面试题 02.08. 环路检测 中，根据官方题解中第二种使用 快慢指针 的方式，可以求得环形链表的环点。
      但是有点费解的是，官方直接在首次相遇后推算出公式 \(a=c+(n−1)(b+c)\)，然后莫名其妙就判定如果此时使用pre和slow指针最终会在环点相遇。

      对于我来理解的话，跨度有点大了。经 大佬视频 的解释，慢慢理解了。

      大概就是：只有在第一次快慢指针相遇后，才能的出公式 \(a=c+(n−1)(b+c)\)，其他时间这个公式不一定成立。而且对于公式中的 n 来说，必定 >= 1，不存在 0 即（快指针还没跑一圈呢，就和慢指针相遇了）的情况。在得出公式后，我们可以知道，在首次相遇后这个时间点，会存在 \(a = c + x圈 \) 这种关系。其中 a 和 c 只是距离问题，和快慢没关系了。所以在 首次相遇 情况下，可以理解为两个人从 a 开头和 c 开头，均速往环点走，一定会在环点相遇，无非是第二个人从 c 点多可能走几圈而已。

  • Reference #

comments powered by Disqus