当前位置：首页 > article >正文

【单链表算法实战】解锁数据结构核心谜题——环形链表

article 2025/1/30 23:45:39

题目如下：

在这里插入图片描述

解题过程如下：

环形链表：尾结点的next指针不为空，而是指向链表中的任一结点。
在这里插入图片描述
思路：快慢指针，慢指针每次走一步，快指针每次走两步。快慢指针在环中追逐相遇，那么这个链表为环形链表；快慢指针没有相遇，那么这个链表不是环形链表。

在这里插入图片描述

完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    //快慢指针，相遇为环形链表，否则不是环形链表
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}

试着证明：

在环形链表中，快慢指针，慢指针每次走1步，快指针每次走2步，在环中追逐一定会相遇。

具体示例画图分析，slow和fast之间的距离变化：1 2 3 2 1 0，3是这里的最大距离。但是，在面试中被问到如何求证，可不能画一个具体例子说明，这就不是证明了！
在这里插入图片描述

slow和fast入环之后，分析追逐的过程中距离的变化，既然一定会存在最大距离，那么假设此时slow刚入环，slow和fast的最大距离为N，之后每追击1次，距离会缩小1步：
在这里插入图片描述

最终slow和fast的距离为0，说明一定会相遇。

在环形链表中，快慢指针，慢指针每次走1步，快指针每次走3/4/5……步，在环中追逐一定会相遇吗？

在环形链表中，慢指针每次走1步，快指针每次走3步，假设此时slow刚入环，slow和fast的最大距离为N，之后每追击1次，距离会缩小2步，在环中追逐的过程中距离的变化：

N为奇数时，下一圈会相遇吗？N为奇数时，下一圈追逐：
当C - 1为偶数时，即C为奇数，一定会相遇；
当C - 1为奇数时，即C为偶数，一定不会相遇。

在这里插入图片描述

上图为例，慢指针每次走1步，快指针每次走3步，快慢指针走过的路程之间的关系：3 * 慢指针 = 快指针

假设：入环结点到头结点的距离是L，此时slow刚刚入环，fast已经在环内绕了n圈。

快慢指针走的路程分别为：
慢指针：L
快指针：L + C - N + nC

根据公式3 * 慢指针 = 快指针：2L = (n + 1)C - N
先分析2L：由于偶数 * 偶数 = 偶数；偶数 * 奇数 = 偶数，所以2L一定是偶数。
已知N为奇数，由于偶数 = 偶数 - 偶数；偶数 = 奇数 - 奇数，所以(n + 1)C一定是奇数，若当中C为偶数，那么(n + 1)C也为偶数，与结论(n + 1)C一定是奇数相悖，所以C一定是奇数。

由于：

N为奇数时，下一圈会相遇吗？N为奇数时，下一圈追逐：
当C - 1为偶数时，即C为奇数，一定会相遇；
当C - 1为奇数时，即C为偶数，一定不会相遇。

综上，在环形链表中，慢指针每次走1步，快指针每次走3步，快慢指针在环中追逐一定会相遇。同理，慢指针每次走1步，快指针每次走4/5/……步，快慢指针在环中追逐也一定会相遇，证明过程同上。

慢指针每次走1步，快指针每次走3步，完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    //快慢指针，慢指针每次走1步，快指针每次走3步
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        int n = 3;
        while (n--)
        {
            if (fast->next)
            {
                fast = fast->next;
            }
            else{
                return false;
            }
        }
        if (slow == fast)
            {
                return true;
            }
    }
    return false;
}