力扣题目链接

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

思路

双指针

定义快慢指针，从head指针开始，快指针每次前进两步，慢指针每次前进一步，第一次相遇后，其中任一个指针指向head指针，然后快慢指针每次前进一步，第二次相遇时的节点就是环开始的节点。

struct ListNode *detectCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL || head->next->next == NULL) {
        return NULL;
    }

    struct ListNode *fast = head;
    struct ListNode *low  = head;

    do {
        low  = low->next;
        fast = fast->next->next;
        if (fast == NULL || fast->next == NULL) {
            return NULL;
        }
    } while (fast != low);

    low = head;

    while (fast != low) {
        low  = low->next;
        fast = fast->next;
    }

    return fast;
}

原理

当快慢指针第一次相遇，慢指针slow走了n步，快指针fast走了2n步,即fast=2*slow；

fast比slow多走了a个环的长度b，即fast=slow+a*b；

能得到slow走了a个环，，即a*b；

而环开始的节点与head的距离应为t+a*b，t为直接入口节点的步数；

能得到slow再走t步就能到环开始的节点，让任一指针回到head，当fast走了t步，到了环开始的节点，slow此时也到了环开始的节点，判断二者相等即可。

最后修改：2024 年 11 月 05 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏