《剑指 Offer》专项突破版 - 面试题 22 : 链表中环的入口节点（C++ 实现）

目录

前言

一、需要知道环中节点数目的解法

二、不需要知道环中节点数目的解法

---

?

---

前言

题目链接：LCR 022. 环形链表 II - 力扣（LeetCode）

题目：

如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着 next 指针方向进入环的第 1 个节点为环的入口节点。例如，在下图所示的链表中，环的入口节点是 3。

分析：

解决这个问题的第 1 步是如何确定一个链表中包含环。如果一个链表中没有环，那么自然不存在环的入口节点，此时应该返回 nullptr。

可以定义两个指针并同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果链表中不包含环，走得快的指针直到抵达链表的尾节点都不会和走得慢的指针相遇。如果链表中包含环，走得快的指针在环里绕一圈之后将会追上走得慢的指针。因此，可以根据一快一慢两个指针是否相遇来判断链表中是否包含环。

---

一、需要知道环中节点数目的解法

第 2 步是如何找到环的入口节点，可以用两个指针来解决。先定义两个指针 P1 和 P2，指向链表的头节点。如果链表中的环有 n 个节点，第 1 个指针 P1 先在链表中向前移动 n 步，然后两个指针以相同的速度向前移动。当第 2 个指针指向环的入口节点时，指针 P1 已经围绕环走一圈又回到了入口节点。

以下图中的链表为例来分析两个指针的移动规律。指针 P1 在初始化时指向链表的头节点。由于环中有 4 个节点，指针 P1 先在链表中向前移动 4 步到达第 5 个节点，如下图 (a) 所示。然后将指针 P2 指向链表的头节点，如下图 (b) 所示。接下来两个指针以相同的速度在链表中向前移动直至相遇，它们相遇的节点正好是环的入口结点，如下图 (c) 所示。

最后一个问题是如何得到环中节点的数目。前面在判断链表中是否有环时用到了一快一慢两个指针。如果两个指针相遇，则表明链表中存在环。两个指针之所以会相遇是因为快的指针绕环一圈追上慢的指针，因此它们相遇的节点一定在环中。可以从这个相遇的节点出发一边继续向前移动一边计数，当再次回到这个节点时就可以得到环中节点的数目。

class Solution {
public:
 ? ?ListNode* getNodeInLoop(ListNode* head) {
 ? ? ? ?ListNode* slow = head;
 ? ? ? ?ListNode* fast = head;
 ? ? ? ?while (fast && fast->next) ?
 ? ? ?  {
 ? ? ? ? ? ?slow = slow->next;
 ? ? ? ? ? ?fast = fast->next->next;
 ? ? ? ? ? ?if (slow == fast)
 ? ? ? ? ? ? ? ?return slow;
 ? ? ?  }
 ? ? ? ?return nullptr;
 ?  }
?
 ? ?ListNode *detectCycle(ListNode *head) {
 ? ? ? ?ListNode* meet = getNodeInLoop(head);
 ? ? ? ?if (meet == nullptr)
 ? ? ? ? ? ?return nullptr;
 ? ? ? ?
 ? ? ? ?int loopCount = 1;
 ? ? ? ?ListNode* cur = meet->next;
 ? ? ? ?while (cur != meet)
 ? ? ?  {
 ? ? ? ? ? ?++loopCount;
 ? ? ? ? ? ?cur = cur->next;
 ? ? ?  }
?
 ? ? ? ?ListNode* front = head;
 ? ? ? ?for (int i = 0; i < loopCount; ++i)
 ? ? ?  {
 ? ? ? ? ? ?front = front->next;
 ? ? ?  }
 ? ? ? ?ListNode* back = head;
 ? ? ? ?while (front != back)
 ? ? ?  {
 ? ? ? ? ? ?front = front->next;
 ? ? ? ? ? ?back = back->next;
 ? ? ?  }
 ? ? ? ?return front;
 ?  }
};

---

二、不需要知道环中节点数目的解法

上述代码需要求出链表的环中节点的数目。如果仔细分析，就会发现其实并没有必要求得环中节点的数目。如果链表中有环，快慢指针一定会在环中的某个节点相遇。慢的指针一次走一步，假设在相遇时慢的指针一共走了 k 步。由于快的指针一次走两步，因此在相遇时快的指针一共走了 2k 步。因此，到相遇时快的指针比慢的指针多走了 k 步。另外两个指针相遇时快的指针比慢的指针在环中多转了若干圈。也就是说，两个指针相遇时快的指针多走的步数 k 一定是环中节点的数目的整数倍，此时慢的指针走过的步数 k 也是环中节点数的整数倍。

此时可以让一个指针指向相遇的节点，该指针的位置是之前慢的指针走了 k 步到达的位置。接着让另一个指针指向链表的头节点，然后两个指针以相同的速度一起朝着指向下一个节点的指针移动，当后面的指针到达环的入口节点时，前面的指针比它多走了 k 步，而 k 是环中节点的整数倍，相当于前面的指针在环中转了 k 圈后也到达环的入口节点，两个指针正好相遇。也就是说，两个指针相遇的节点正好是环的入口节点。

class Solution {
public:
 ? ?ListNode* getNodeInLoop(ListNode* head) {
 ? ? ? ?ListNode* slow = head;
 ? ? ? ?ListNode* fast = head;
 ? ? ? ?while (fast && fast->next) ?
 ? ? ?  {
 ? ? ? ? ? ?slow = slow->next;
 ? ? ? ? ? ?fast = fast->next->next;
 ? ? ? ? ? ?if (slow == fast)
 ? ? ? ? ? ? ? ?return slow;
 ? ? ?  }
 ? ? ? ?return nullptr;
 ?  }
 ? ?
 ? ?ListNode *detectCycle(ListNode *head) {
 ? ? ? ?ListNode* front = getNodeInLoop(head);
 ? ? ? ?if (front == nullptr)
 ? ? ? ? ? ?return nullptr;
 ? ? ? ?
 ? ? ? ?ListNode* back = head;
 ? ? ? ?while (front != back)
 ? ? ?  {
 ? ? ? ? ? ?front = front->next;
 ? ? ? ? ? ?back = back->next;
 ? ? ?  }
 ? ? ? ?return front;
 ?  }
};