第7天｜环形链表 Ⅱ

张开发
• 2026/4/20 8:42:01 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

第7天｜环形链表 Ⅱ
一、今日题目142. 环形链表 II今日任务 142. 环形链表 II 总结链表与数组的适用场景差异提交第一周学习小结 题意 给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 null。为了表示给定链表中的环使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。说明不允许修改给定的链表。 题目链接 https://leetcode.cn/problems/linked-list-cycle-ii/视频链接 https://www.bilibili.com/video/BV1if4y1d7ob二、解题思路快慢指针法这是解决链表环问题的最优解法时间复杂度O(n)空间复杂度O(1)分为两步1. 判断有环找相遇点初始化快指针fast每次走2步、慢指针slow每次走1步均指向头节点。 快指针先到末尾说明无环两指针在环内相遇说明有环。2. 找入环的第一个节点,相遇后将快指针移回表头快慢指针均每次走1步, 再次相遇的节点就是入环的第一个节点。三、代码实现四、 常见易错点1. 链表操作容易丢指针、成环一定要一步步推演节点走向。2. 边界条件容易忽略空链表、单个节点、无环场景。3. 二分法的区间规则不熟练容易陷入死循环。

更多文章