单链表算法 - 环形链表II

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/linked-list-cycle-ii/description/思路:

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
typedef struct ListNode ListNode;
 
ListNode* findMidNode(ListNode* head)
{
    //定义两个指针
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
            return slow;
    }
    return NULL;
}
 
struct ListNode *detectCycle(struct ListNode *head) {
    //找环的相遇点
    ListNode* meet = findMidNode(head);
    //从头节点和相遇节点开始遍历,每次走一步
    ListNode* pcur = head;
    while(meet && pcur)
    {
        //当指针相遇的节点,即环的入口节点
        //相遇点和头节点到入环的位置是相等的
        if(meet == pcur)
        {
            return pcur;
        }
        meet = meet->next;
        pcur = pcur->next;
    }
    //代码走到这就说明链表不成环
    return NULL;
}

 提交结果:

那么为什么相遇点和头节点到入环节点的距离是相等的。