环形链表Ⅱ

描述

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

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

题解

这个问题的解决方法是使用 “快慢指针”（也称为 “龟兔赛跑算法”）。我们使用两个指针，一个指针每次移动一个节点，另一个指针每次移动两个节点。如果链表中有环，那么这两个指针最终一定会相遇。

当两个指针相遇时，我们可以确定链表中有环。接下来，我们需要找到环的起点。我们可以使用两个指针，一个指针从链表头开始，另一个指针从相遇点开始。这两个指针每次都只移动一个节点，当它们相遇时，就是环的起点。

如果链表中没有环，那么快指针最终会到达链表的末尾，此时我们可以直接返回 nullptr。

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        // 首先使用快慢指针找到链表中的环
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }
        // 如果链表中没有环，则直接返回 nullptr
        if (fast == nullptr || fast->next == nullptr) {
            return nullptr;
        }
        // 如果链表中有环，则找到环的起点
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};