当前位置：首页 > article >正文

LeetCode 142 - 环形链表 II

article 2024/10/23 21:41:49

题目描述

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

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

不允许修改链表。

解题思路

要解决这个问题，我们需要判断链表是否有环，并找出环的起始位置。我们可以使用弗洛伊德的“龟兔赛跑”算法（双指针法）完成这个任务，该算法包含以下两个主要步骤：

判断链表是否有环：
- 使用一个慢指针 slow 和一个快指针 fast。
- slow 每次移动一步，fast 每次移动两步。
- 如果两个指针相遇，则链表中存在环。
- 如果 fast 或 fast->next 为空，则链表无环。
找到环的起始位置：
- 当发现 slow 与 fast 相遇时，将其中一个指针重新指向链表头节点 head。
- 两个指针每次都移动一步，当它们再次相遇时，相遇点即为环的起始位置。

具体算法如下：

算法实现

C++实现

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};