环形链表问题（图 + 证明 + 题）

时间：2024-11-11 08:14:28

文章目录

  • 判断链表是否有环
  • 返回链表开始入环的第一个结点

判断链表是否有环

题目链接

在这里插入图片描述

思路：

可以明确的是：若一个链表带环，那么用指针一直顺着链表遍历，最终会回到某个地方。

我们可以定义两个指针（快慢指针），两个指针均从表头开始同时遍历链表，快指针一次走两步，慢指针一次走一步。如果链表带环，那么快慢指针一定会相遇，否则快指针会先遍历完链表（遇到NULL）。
eg ：

代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                return true;
        }
        return false;
    }
};

返回链表开始入环的第一个结点

题目链接

在这里插入图片描述

思路 ：

让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

证明如下：

在这里插入图片描述
根据最终推论可以得出结论：若一个指针从出发点开始走，另一个指针从相遇点开始走，则他们最终会在入口点处相遇。

代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            {
                ListNode* meet = fast;
                while(meet != head)
                {
                    meet = meet->next;
                    head = head->next;
                }
                return meet;
            }
        }
        return NULL;
    }
};

为什么慢指针走一步，快指针走两步，他们一定会在环里面相遇？会不会永远追不上？请证明。

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况。
因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

在这里插入图片描述

快指针一次走3步，走4步，…n步行吗？

不行，这样可能会追不上，证明如下：

在这里插入图片描述
总结一下：
 当慢指针走一步，快指针走三步时。若慢指针进环时与快指针之间的距离为奇数，并且环的周长恰好为偶数，那么他们会一直在环里面打转转，永远不会相遇。
（当慢指针走一步，快指针走四步或是走n步时，证明过程类似）

相关文章