找出链表环的入口节点

"环形链表 II 的问题及解法" 环形链表 II 是一道经典的算法题，主要考察的是链表处理和循环检测的能力。在实际的编程面试或算法竞赛中，这类问题经常出现，因为它有助于理解数据结构的基础概念以及如何高效地遍历和操作链表。 题目要求找到一个链表中环的起始节点。如果链表有环，用整数 pos 表示环的入口位置，如果 pos 为 -1，则链表没有环。需要注意，pos 只是一个辅助信息，不会作为函数参数传入，我们需要通过遍历链表自行判断环的存在。 给定的示例展示了不同情况下的链表环： 1. 示例1中，环的入口在第二个节点，即 pos=1，链表的尾部与第二个节点相连。 2. 示例2中，环的入口在第一个节点，即 pos=0，链表的尾部与第一个节点相连。 3. 示例3中，pos=-1 表示链表没有环。 解法通常使用快慢指针（Floyd's Tortoise and Hare Algorithm），也称为龟兔赛跑算法。在这个问题中，我们定义两个指针 slow 和 fast，初始时都指向链表头。slow 指针每次移动一个节点，fast 指针每次移动两个节点。如果链表中存在环，那么快指针最终会追上慢指针（形成相遇点），因为快指针的速度是慢指针的两倍。相遇后，我们可以再定义一个新的指针 ptr，让它从头节点开始，每次移动一个节点，直到它与慢指针相遇，这个相遇点就是环的入口。 以下是 C++ 实现的参考代码： ```cpp 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 (fast == slow) { ListNode* ptr = head; while (ptr != slow) { ptr = ptr->next; slow = slow->next; } return ptr; // 相遇点即为环的入口 } } return nullptr; // 未发现环，返回 null } }; ``` 这段代码首先用快慢指针检查环的存在，然后通过 ptr 指针重新从头节点开始寻找环的入口。这种方法确保了即使链表很大，也能在 O(n) 时间复杂度内解决，其中 n 是链表的总节点数。 在实际应用中，理解和掌握这类问题对于解决更复杂的链表问题至关重要，例如查找链表中间节点、反转链表、合并两个有序链表等。同时，这也是一种很好的思维锻炼，能提高对数据结构和算法的理解。