Leecode之环形链表进阶

一.题目及剖析

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

这道题就是找到链表中环的入口

二.思路引入

假设起点到环的入口的距离为L, 环的长度为C, 入口到相遇点的距离为C - N

设定一个快慢指针,速度分别为2, 1

则有 (L + kC - N) = 2*(L + C - N)

即L = (k - 1)C + N

说明,如果我设定两个速度相同的指针,一个从起点开始遍历,一个从相遇点开始遍历,那么它们会在入口处碰撞

三.代码引入

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

四.思路扩展

这道题如果将这个带还链表从相遇点断开,那么其实就是一个相交链表,交点就是环的入口