LeetCode 142. 环形链表 II（C 语言实现）

LeetCode 142. 环形链表 II

一、题目介绍

本题要求返回链表开始入环的第一个节点。如果链表无环，则返回 NULL。

二、题目详解

1. 审题

题目要求返回链表开始入环的第一个节点。首先需判断该链表是否为环形链表，如果不是，直接返回 NULL；若是环形链表，则需找出入环节点。

2. 判断是否为环形链表

（1）思路

如果链表不为环形链表，遍历链表一定会走到空指针。如果是环形链表，遍历将会陷入死循环。可以使用快慢指针法：一个快指针每次走 2 步，一个慢指针每次走 1 步。如果是环形链表，快指针最终会在环中追上慢指针；如果不是环形链表，快指针会先到达空指针。

（2）代码演示

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            return findEntry(head, fast);
        }
    }
    return NULL;
}

3. 找到入环节点

（1）思路

已知是环形链表，如何找到入环节点？ 设环的长度为 C，非环的长度为 L，相遇点与入环节点的距离为 N。

快指针走的总距离：L_fast = L + N + x * C (x 为 fast 走的圈数) 慢指针走的总距离：L_slow = L + N

因为 fast 速度是 slow 的两倍，所以 L_fast = 2 * L_slow。 代入得：L + N + x * C = 2 * (L + N) 化简得：x * C = N + L 变式得：(x - 1) * C + C - N = L

左式相当于一指针走了 (x-1) 圈再加上 C-N，右式就是头节点到入环节点的距离。因此，让一个指针 meet 从相遇点开始走，让一个指针 cur 从头节点开始走，当 meet 在环内走了 (x-1) 圈时，再走 C-N 距离就会与走了 L 距离的 cur 相遇。

（2）代码演示

创建 meet 和 cur，分别从相遇点和头节点开始以相同速度走，相遇点即为入环节点。

struct ListNode* findEntry(struct ListNode* head, struct ListNode* meet) {
    struct ListNode* cur = head;
     () {
         (meet == cur) {
             meet;
        }
        meet = meet->next;
        cur = cur->next;
    }
}