什么是环形链表？

环形链表是一种特殊类型的链表结构，其最后一个节点的 next 指针指向链表中前面的某个节点，而不是通常情况下连接到空指针(NULL)，形成了一个闭环。如图：

由于链表最后一个节点的 next 指针没有指向 NULL，而是指向前面的某一个节点，所以我们不能再用current->next == NULL作为结束的判断条件来遍历链表（这样会造成死循环），通常使用快慢指针来控制结束条件，下面的两个题目都是要借助快慢指针来实现。

（一）检测一个链表是否有环

先来说一下结论，如何判断一个链表是否有环：

  1. 首先，让快指针 fast、慢指针 slow 都指向链表的头节点 Head；
  2. 在遍历过程中，快指针 fast 一次向后移动两个节点，慢指针 slow 一次向后移动一个节点；
  3. 判断 fast 和 slow 是否会相遇在同一个节点上：
    1. 如果移动到同一个节点上，说明链表有环，返回true；
    2. 如果还没有移动到同一个节点上，继续执行步骤2
  1. 上几个步骤通过循环完成，循环的结束条件是 fast 或者 fast->next 指向 NULL。
  2. 如果循环结束，fast 和 slow 还没有相遇，则说明链表不存在环形结构，返回 false。

代码如下：

struct ListNode* fast, *slow;
fast = slow = head;
while(fast && fast->next)
{
    slow = slow->next;
    fast = fast->next->next;
    if(slow == fast)
        return true;
}
return false;

分析

1、为什么循环的结束条件是 fast/fast->next 指向NULL？

  • 当一个链表中有环时，fast 和 fast->next 永远不会指向 NULL
  • 当一个链表中没有环时，fast 一定会先移动到链表的结尾（fast 一次移动两个节点）；又因为 fast 一次移动两个节点，所以有两种情况：
    • fast 移动两次后，刚好指向NULL，结束循环；
    • fast移动一次后就已经指向NULL，此时再进行移动，就会出现对NULL的解引用，此时也结束循环

2、为什么要求快指针fast一次移动两个节点，慢指针slow一次移动一个节点？

快指针 fast 和慢指针 slow，两者一定会相遇吗？

移动的过程中有一下三种状态：

1）快指针 fast 和慢指针 slow 都还没有进入环（4号节点是环的入口点）

2）快指针 fast 进入环的（过了环的入口点）、慢指针 slow 没有进入环

3）快指针 fast 和慢指针 slow 都在环内

为了方便画图和不失一般性，需要将链表抽象出一个模型来说明。并且如果链表存在环，快指针 fast 和慢指针slow 一定是在环内相遇（fast 会先进入环，如果此时 slow 还没进入环，fast 就会在环内循环），所以我们主要分析一下第三种状态。

因为当 slow 进入环后，因为 fast 移动的速度快，所以可以看成 fast 追 slow，当 fast 逐渐减少两者的距离，如果两者的距离为0，两者就相遇了。因为从 fast 追 slow 的角度来看，所以两者的距离为：

此时 fast 和 slow 的距离设为 N，当 fast 和 slow 每移动一次，两者的距离就会变成 N - 1（fast 向前移动两个节点，slow 向前移动一个节点，所以距离就近一个节点），也就是移动一次两者的距离就 -1。

如此往复，N-1-1-1-1-1-1-1-1-……，N 会被减为0，两者就相遇了。

所以，快指针fast一次移动两个节点，慢指针slow一次移动一个节点时，两者一定会相遇。

fast一次不能移动三个/四个节点吗？

可以用同样的分析方法，来分析一下fast一次移动三个/四个节点的情况。

1）fast一次移动三个节点的情况：

此时 fast 和 slow 的距离设为 N，当 fast 和 slow 每移动一次，两者的距离就会变成 N-2 ，所以N-2-2-2-2-……

不难发现，如果是两者每移动一次距离减2的话，可能会出现N不会减到0的情况，需要根据 N 的是否是2的倍数来讨论：

① N为2的倍数时

N可以被减到零，快慢指针会相遇；

在相遇前的最后一步，两者的距离为 2，是2的倍数：

此时 fast 再向前移动 3 个节点、slow向前移动 1 个节点时，两者就相遇了：

② N不为2的倍数时

N不会被减到 0，当两者的距离 N 等于1时，

此时 fast 再向前移动 3 个节点、slow向前移动 1 个节点时，两者就完美的错过了（＞﹏＜）：

fast 会领先 slow 一圈，这时 fast 会跑到 slow 的前面一个节点，两者的距离会变成 C-1（设C为环的长度）。

然后 fast 和 slow 会继续移动，fast 同样追赶 slow，（C-1）-2-2-2-2-…… 到这里又有两种情况，（C-1）是否是2的倍数：

  • 如果（C-1）是2的倍数， fast 就可以和 slow 相遇；
  • 如果（C-1）不是2的倍数，后面 fast 还会完美错过 slow，然后重复上述过程，两者就不会相遇了。

所以 fast 一次移动三个节点，fast 和 slow 不一定会相遇，它有两个影响点：

  • 与环的长度有关，需要判断（C-1）是否是2的倍数，如果是就可以相遇，否则就不能相遇；
  • 环入口点之前节点的个数有关，N 是否是2的倍数。在 slow 还没有到达环入口点前，fast 会在环内一直循环，环入口点之前节点的个数不同，当 slow 到达环入口点时，fast 的与 slow 的相对位置也会有所不同，也就是 N 不同。
2）fast一次移动四个节点的情况

fast 一次移动四个节点的分析方法与上述相同，下面我就直接ctrl + c和ctrl + v了：

fast 和 slow 的距离设为 N，当 fast 和 slow 每移动一次，两者的距离就会变成 N-3 ，所以N-3-3-3-3-……

不难发现，如果是两者每移动一次距离减3的话，可能会出现N不会减到0的情况，需要根据 N 的是否是3的倍数来讨论：

① N为3的倍数时

N可以被减到零，快慢指针会相遇；

在相遇前的最后一步，两者的距离为 3，是3的倍数：

此时 fast 再向前移动 4 个节点、slow向前移动 1 个节点时，两者就相遇了：

② N不为3的倍数时

N不会被减到 0，当两者的距离 N 等于 2 时，

此时 fast 再向前移动 4 个节点、slow向前移动 1 个节点时，两者就完美的错过了（＞﹏＜）：

fast 会领先 slow 一圈，这时 fast 会跑到 slow 的前面两个节点，两者的距离会变成 C-1（设C为环的长度）。

然后 fast 和 slow 会继续移动，fast 同样追赶 slow，（C-1）-3-3-3-3-…… 到这里又有两种情况，（C-1）是否是3的倍数：

  • 如果（C-1）是3的倍数， fast 就可以和 slow 相遇；
  • 如果（C-1）不是3的倍数，后面 fast 还会完美错过 slow，然后重复上述过程，两者就不会相遇了。

所以 fast 一次移动四个节点，fast 和 slow 不一定会相遇，它有两个影响点：

  • 与环的长度有关，需要判断（C-1）是否是3的倍数，如果是就可以相遇，否则就不能相遇；
  • 环入口点之前节点的个数有关，N 是否是3的倍数。在 slow 还没有到达环入口点前，fast 会在环内一直循环，环入口点之前节点的个数不同，当 slow 到达环入口点时，fast 的与 slow 的相对位置也会有所不同，也就是 N 不同。

（二）寻找环的入口点

这里还是先说明一下结论：

  1. 用两个指针cur1、cur2分别指向链表的头节点和快慢指针相遇的节点；
  2. 同时移动两个指针
  3. 当两个指针指向同一个节点时，该节点就是环的入口点
struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode* fast, *slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            struct ListNode* meet = slow;
            struct ListNode * cur = head;
            while(meet != cur)
            {
                meet=meet->next;
                cur = cur->next;
            }
            return meet;
        }
    }
    return NULL;
}

设直线链表的长度为 L、环的长度为 C、快慢指针相遇点距离环入口点的距离为 X：

  • 当慢指针slow到达相遇点时，slow走过的距离为 L+X
  • 快指针fast走过的距离为 L+X+N * C （N是 slow 未到达环入口点时，fast 所走过环的圈数， N大于等于1）

slow走过的距离为什么是 L+X？

slow 走过的距离为什么是 L+X， 而不是 L+X+圈数？即 slow 不会走环的一圈+X？

我们先来看一下极端情况，假设 fast 和 slow 指针同时从环的入口点出发：

由小学数学可以知道，相同的起点，fast 的速度是 slow 速度的二倍，在相同的时间下， fast 走过的距离是 slow的二倍，所以当 slow 完整走了一圈回到起点时，fast 刚好第二次回到起点，此时两者相遇，而 slow 也只是走了一圈。

由于走过前面 L 长度的节点后，fast 和 slow 之间一定有距离，所以当 slow 到达环的入口点时，fast 可能不在环的入口点，所以slow肯定不会走一圈的。

fast走过的距离为什么是 L+X+N*C，并且N大于等于1？

这里的 N 是指 fast 在 slow 还没到到环的入口点时，走过的圈数。

这里先解释一下 “N * C，并且N大于等于1”。由于 slow 一次移动一个节点，fast 一次移动两个节点，相同的时间下，fast 的速度大于 slow 的速度，两者走过的距离肯定不相同（slow 进入环时，fast 已经在环内了），所以 fast 在走第一圈内，slow 和 fast 不会相遇，只有当 fast 超过slow 一圈或几圈后，两者才能相遇。

L == Y

  1. 又因为 fast 走过的距离是 slow 走过距离的二倍，所以有：L+ X  +N * C = 2 *（L+X）
  2. 进一步化简得：N * C = L+X
  3. 这里再把左边的 N 拿出来一个：（N-1）* C + C = L + X
  4. 又因为 fast 在环上走（N - 1）圈，但 fast 与 slow 相遇点距离起始点的相对位置不变，所以得到下式：C = L + X
  5. 进一步得到：L=  C - X = Y 

因为 Y == L，所以让两个指针同时移动，它俩就能相遇在环的入口处。

代码

当然基 Y == L这一结论，还可以 让快慢指针相遇点与下一个节点断开，然后将问题转化为两个链表的相交，环的入口点其实就是两个链表的相交点。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    if(headA==NULL && headB==NULL)
    {
        return NULL;
    }
    struct ListNode* curA = headA, * curB = headB;
    int count1 = 0, count2 = 0;
    while (curA->next != NULL)
    {
        count1++;
        curA = curA->next;
    }
    while (curB->next != NULL)
    {
        count2++;
        curB = curB->next;
    }
    int gap = abs(count1 - count2);
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if (count1 < count2)
    {
        longlist = headB;
        shortlist = headA;
    }
    if (curB == curA)
    {
        while (gap--)
        {
            longlist = longlist->next;
        }
        while (longlist != shortlist)
        {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
        return longlist;
            
    }
    else
    {
        return NULL;
    }
}

struct ListNode* getmeetnode(struct ListNode* head)
{
    struct ListNode* fast, * slow;
    fast = slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return fast;
        }
    }
    return NULL;
}
struct ListNode* detectCycle(struct ListNode* head)
{
    // 找到相遇点
    
    struct ListNode* meetnode = getmeetnode(head);
    if(meetnode == NULL)
    {
        return NULL;
    }
    // 断开为两个链表
    struct ListNode* cur1, *cur2;
    cur1 = meetnode->next;
    meetnode->next=NULL;
    cur2 = head;

    // 找到两个链表的交点
    struct ListNode* IntersectionNode = getIntersectionNode(cur1, cur2);
    return IntersectionNode;

}

本次内容到此结束了！如果你觉得这篇博客对你有帮助的话 ，希望你能够给我点个赞，感谢感谢……

# 链表 # 数据结构
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

Electron 主进程与渲染进程通信详解：HarmonyOS PC基于 `ipcRenderer.send` 与 `ipcMain.on` 的双向数据传输

avatar 2048 AI社区
cover

37岁北漂程序员因职业倦怠决定转行大模型

avatar 2048 AI社区
cover

LangChain与LangGraph：让大模型开发更简单，小白也能轻松掌握（收藏必备）

avatar 2048 AI社区