题目说明

题目：LeetCode 142. 环形链表 II

要求：给定一个链表头节点 head，判断链表是否有环；如果有环，返回环的入口节点；如果没有环，返回 nullptr。

方法一：快慢指针（Floyd 判圈）

思路

先用快慢指针判断是否有环：

  1. 慢指针每次走 1 步，快指针每次走 2 步。
  2. 如果链表无环，快指针会先到达 nullptr。
  3. 如果有环，快慢指针一定会在环内相遇。

1775839182380.png

相遇后，再从头节点出发一个指针，同时从相遇点出发一个指针，二者每次都走 1 步，再次相遇的位置就是环的入口。

为什么能找到入口

设：

  • 头节点到环入口距离为
  • 环入口顺时针到相遇点距离为
  • 相遇点顺时针到环入口距离为
  • 环长度为

已知：

联立得：

等价写法：

因此：

（即 ）

结论：
从相遇点再走 （模环长意义下）与从头结点走 ，都会到达环入口；所以一个指针从头出发、一个从相遇点出发，同速前进，必在入口相遇。

代码

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

    while (fast != nullptr && fast->next != nullptr) {
      fast = fast->next->next;
      slow = slow->next;

      if (fast == slow) {
        ListNode *index1 = head;
        ListNode *index2 = fast;

        while (index1 != index2) {
          index1 = index1->next;
          index2 = index2->next;
        }

        return index1;
      }
    }

    return nullptr;
  }
};

复杂度分析

  • 时间复杂度：
  • 空间复杂度：

方法二：哈希表

思路

用哈希表记录访问过的节点地址：

  1. 遍历链表。
  2. 如果当前节点已存在于哈希表中，说明再次访问到了同一个节点，即存在环，且当前节点就是环入口。
  3. 如果不存在，则加入哈希表并继续遍历。

代码

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        unordered_set<ListNode*> visited;

        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }

            visited.insert(head);
            head = head->next;
        }

        return nullptr;
    }
};

复杂度分析

  • 时间复杂度：
  • 空间复杂度：

总结

这题的核心是掌握 Floyd 判圈 + 数学关系推导入口。面试和笔试中更推荐方法一，因为它在时间复杂度相同的情况下只用常数额外空间；方法二更直观，适合快速验证思路。刷到链表环问题时，优先联想到快慢指针，通常就离 AC 不远了。