跳转至

142 环形链表II

leetcode

思路

  1. 判断链表是否有环
  2. 本题还需要找环的入口,通过推理我们得到:相遇后,设定一个指针在head起始位置,另一个在相遇位置,两个指针同时走相同步数一定能在环入口相遇

推导过程:

  1. 假设head到环的起点距离为a,环的长度为len
  2. 第一次到环的起点,毫无疑问只有fast(fast走的距离是slow两倍,slow追不上fast)
  3. 第二次到环的起点,slow一定到达。fast不一定到达
    1. 如果len恰好等于a,由于fast走的距离是slow两倍,fast走2a = a + len,fast恰好到达环的起点与slow相遇,那么slow和fast在环的起点相遇,得到问题的解
    2. 否则,无论len < a或者len > a,fast一定不在环的起点,并且与环的起点/slow相距k(k一定小于len)
  4. 我们讨论len != a的情况,由于slow和fast相距k(k < len),两者需要多久相遇呢,给出结论:一圈内。这是因为k < len,fast每次都比slow多走一步,所以fast追上slow需要走k步,而k < len。
  5. 我们已经知道slow和fast下次相遇在一圈内(这解释了为什么slow一定走a + m)。请注意:此时只是第二次到达环的起点,还没到第三次。这意味着slow还没走环 假设两者相遇,此时slow走了a + m步, fast走了2(a + m)步,有等式2(a + m) == a + m + n * len(n为fast走过的环的圈数),化简得到a == (n - 1) * len + len - m
  6. len - m实际上是fast到环的起点的距离,因此我们可以知道,让slow从head开始,fast仍然在原来的位置,fast和slow同时移动,slow到达环的起点走的a步 == fast到达环的起点走的len - m步,两者相遇在环的起点

综上所述:

  1. 无论环的长度len与head到环的起点a的大小关系如何,两者第一次相遇之后令slow = head,第二次两者一定相遇在环的起点
  2. slow进入环的起点后,slow和fast一定在一圈内相遇,所以slow走的步数一定为a + m,而不是a + m + u * len(u为slow经过环的次数)

推导过程参考

Solution

/**
 * 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, * slow = head;
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                break;
        }
        // 没有环的情况:
        // 1. 没有元素,fast == nullptr
        // 2. 只有一个元素,fast->next == nullptr
        // 3. 递归思想,假设遍历了若干元素并且没有环,剩余元素一定为情况1或情况2
        if(fast == nullptr || fast->next == nullptr){
            return nullptr;
        }
        // 否则有环,此时fast == slow两指针在环内相遇
        // 假设slow走了k,那么fast走了2k,比slow多走了k,k刚好是圈长度的整数倍(k = n * size)
        // 假设环入口离相遇点为m,那么slow从头走到环入口需要k - m,而fast走到环入口路程也为k - m
        // 因此让slow从head开始走,fast和slow走相同距离
        slow = head;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};