环形链表查找入环节点

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。
  

问题展示

一. 前言

  在我的前一篇博客中已经分析过如何判断链表是否带环，如需了解请直达

                 链表带环问题之判断链表是否带环


  下面我们来了解一下如何查找到链表的入环点。

二. 查找入环节点

2.1. 查找方法

  我们不再对判断链表是否带环进行讨论，我们直接快进到快慢指针已经在环中相遇的时间节点：

  如有不解请查看：
  链表带环问题之判断链表是否带环


  在此基础上，我们指定一个 point 代表我们查找的入环节点，让 point 指向链表的开头，再此基础上我们让 point 和 slow 以同样的速率进行前进，也就是每次前进一个节点。

  当 point 和 slow 相遇时，point 指向的就是 入环的节点。

2.2. 解析

  在上述解决办法中，我们通过让 point 指针和 slow 指针 同时以相同速率位移得到入环节点，那其中的原理是什么呢？
  下面我将逐步解析：
  首先是 fast 与 slow 走过的路程：
  在上述办法中，开始时我们让 fast 和 slow 以 2：1的速率进行前行，假设 slow 刚刚到达环节点，此时我们记 slow 走过的路程为 L，如下图所示：

  而此时我们假设fast已经在环内走了 x 圈，假设一圈大小为 C ，并且此时 fast 要再次与 slow 相遇的话，它们之间的距离为 N ，如下图所示：

  此时我们很容易推算出来 fast 走过的路程为：L + ( x + 1 ) * C - N

  而 fast 要追上 slow 还有 N 的路程需要走

  而因为 fast 与 slow 速率比为 2 ：1，故当slow进入环时，fast 与 slow 同时在环内进行移动操作，每一次位移都会让它们之间的距离缩小 1，及需要追赶的路程从 N 变为 N - 1，依次逐步，直到为0。
  即N - 2
   N - 3
   N - 4
   ……
    2
    1
    0

  当 fast 追上 slow 时,
   slow 走过的路程为：L + N
   fast 走过的路程为 L + ( X + 1 ) * C + N = 2L + 2N
  故此时 slow 距离入环点 还有 C - N 的距离。
  如下图所示：

  而在上面分析中 通过 fast 走过的路程 L + ( X + 1 ) * C + N = 2L + 2N，可以推算出 L = ( X + 1) * C - N，即 L = X * C + C - N，故当 point 从头节点出发，走过 L 后到达入环点，此时 slow 又从它与 fast 相遇的位置走了 X 圈环后，又走了 C - N的距离，即此时 slow 也刚好到达入环点，也就是此时 point 与 slow 相遇，此时的 point 就为入环点。

三. 代码展示

  代码展示如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode, * pListNode;
struct ListNode* detectCycle(struct ListNode* head)
{
    pListNode slow = head;
    pListNode fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            pListNode point = head;
            while (point != slow)
            {
                point = point->next;
                slow = slow->next;
            }
            return point;
        }
    }
    return NULL;
}

四. 结语

  十分感谢您观看我的原创文章。
  本文主要用于个人学习和知识分享，学习路漫漫，如有错误，感谢指正。
  如需引用，注明地址。