力扣 142 环形链表Ⅱ给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。示例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出返回索引为 0 的链表节点解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出返回 null解释链表中没有环。提示链表中节点的数目范围在范围[0, 104]内-105 Node.val 105pos的值为-1或者链表中的一个有效索引这道题跟着逻辑走思路很清晰但实际上需要严谨证明和反复琢磨才能真正理解并独立解题主要解决两点判断链表是否成环如果有环那么环的入口在哪里一. 是否成环这里可以采用双指针分别定义快慢指针均从头节点出发其中fast每次移动两个节点而slow每次移动一个节点如果fast和slow在移动途中相遇说明该链表成环。为什么快慢指针相遇就说明成环因为是快指针先入环慢指针后入环如果fast指针和slow指针相遇的话一定是在环中相遇在环内相遇就说明肯定成环了。为什么有环一定会相遇本质上是因为两指针存在速度差在环内绕环移动时快指针一定会追上慢指针。这是因为fast走两步slow走一步对slow来说fast是一点一点接近它的所以两者一定会在环内某一节点处相遇。画一个环让fast在任意一个节点开始追赶slow会发现展开后都是下图这种情况此时按照定义fast往前走一次两步slow走一次一步两者就会在 3 处相遇。完整动画演示如下图二. 入口在哪里假设从头结点到入口节点的节点数为x入口节点到两指针相遇节点的节点数为y从相遇节点再到入口节点的节点数为z 如图所示slow指针走过的节点数为x yfast指针走过的节点数为x y n * (y z)其中n表示快指针追慢指针的过程中绕过的圈数。由于快指针一次走两个节点慢指针一次走一个故快指针走过的节点数是慢指针的2倍。也就是2 * (x y) x y n * (y z)两边消一个x y化简得x y n * (y z)。要找到是环形入口节点也就是x所以把x提出来放左边得x n * (y z) - y。右边提一个y z出来化简得x (y z) * (n - 1) z。化简到这一步不妨设环绕圈数n为1即可得x z。这也就是说从头结点和相遇节点同时出发一个指针两个指针每次只走一个节点 那么当这两个指针相遇时所在处就是环形入口的节点。那么**n如果大于1** 是什么情况呢其实这种情况和n为1的时候是一样的一样可以通过这个方法找到入口节点只不过index1指针在环里多转了(n-1)圈然后再遇到index2相遇点依然是环形的入口节点。至此我们完成了一开始提出的两个问题✅下面是完整力扣代码class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast head; ListNode* slow head; while(fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode* index1 fast; ListNode* index2 head; while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index2; } } return nullptr; } };
