【C】链表算法题7 -- 环形链表||

leetcode链接https://leetcode.cn/problems/linked-list-cycle-ii/description/

问题描述 

  给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

示例1

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例2

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点

思路

  这道题可以沿用上一个环形链表的思想（快慢指针法），上一篇文章中证明了如果链表中有环，那么 fast 指针与 slow 指针一定可以在环中相遇，而在有环链表中还有一个结论，那就是相遇节点与头节点每次都走一步，他们必然会在入环处相遇（证明在代码之后）。

  有了这个结论之后，这道题就很好解决了，我们只需要先判断链表是否有环（上一个环形链表算法题），如果没有环，那么就返回NULL；如果有环，那么找到相遇节点 interNode 之后，然后定义一个节点指针 pcur 指向头节点，如果 pcur 与 interNode 不相同，那么就让 pcur 与interNode 同时往后走，直到他们两相等为止，入环的第一个节点即为 pcur。

代码1

 typedef struct ListNode ListNode;
 //相交结点
 ListNode* IntersectionNode(ListNode* head)
 {
    ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            return slow;
        }
    }
    return NULL;
 }

//入环的第一个节点
struct ListNode *detectCycle(struct ListNode *head) 
{
    //先找相交节点
    ListNode* interNode = IntersectionNode(head);

    if (interNode == NULL)
    {
        return NULL;
    }

    //相遇节点与首结点每次走一步可以在入环处相遇
    ListNode* pcur = head;
    while (pcur != interNode)
    {
        interNode = interNode->next;
        pcur = pcur->next;
    }
    return interNode;
}

 代码2

  当然，上述代码还可以改进一下。不难发现，其实 fast 与 slow 相遇之后，interNode 就是 slow （fast 也可以），所以可以直接用 slow 来作为相遇节点。

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) 
{
    ListNode* fast = head, *slow = head;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if (fast == slow)
        {
            //相遇了，说明有环
            ListNode* pcur = head;
            while (pcur != slow)
            {
                //相遇节点与首结点每次走一步可以在入环处相遇
                pcur = pcur->next;
                slow = slow->next;
            }

            return slow;
        }
    }

    return NULL;
}

证明 

  这里将链表抽象为以下结构（假设fast一次走两步，slow一次走一步）：

设头节点为H，入环的第一个节点为E，fast 与 slow 相遇节点为M，H 到 E 距离为 L，E 到 M 距离为 X，环的周长为 R，所以 E 到 M 的距离就是 R - X ，再假设 fast 与 slow 相遇之前，fast 已经在环内走了 n 圈了，所以在相遇之前， fast 所走过的路程为：L + nR + X；而 slow 所走过的路程为：L + X，为什么 slow 没有绕环呢，因为在 slow 进入环后，fast 与 slow 的距离是越来越近的，他们俩的最大距离就是环的距离，而他们之间的距离又是越来越近的，所以 fast 是会在 slow 进入环之后的一圈内必然是会追上 slow 的。

  由于 fast 一次走两步，slow 一次走一步，所以 fast 所走的路程是 slow 所成路程的两倍，所以有如下这个等式：

  L + nR + X  = 2 * (L +X)

移项就可以得到：

  nR = L + X    =>   L = nR - X    =>    L =  (n - 1)R + R - X

这个等式也就表明，当 slow 到达相遇节点 M 之后，再绕环走 n - 1 圈，头节点也就到达了与 E 相距 R - X 的节点处；此时，slow 回到相遇点，与 E 的距离也是 R - X。所以相遇节点与头节点每次都走一步，他们必然会在入环处相遇。