算法训练营第七天|142.环形链表Ⅱ

张开发
• 2026/4/20 21:28:46 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

算法训练营第七天|142.环形链表Ⅱ
题目链接https://leetcode.cn/problems/linked-list-cycle-ii/视频链接https://www.bilibili.com/video/BV1if4y1d7ob题目描述测试用例算法描述这个算法的目标是给定一个单链表的头节点 head找到并返回链表的中间节点。如果链表有两个中间节点则返回第二个。核心思想快慢指针这个算法的核心思想是定义两个指针从链表的头节点同时出发慢指针 (slow)每次向后移动一个节点。快指针 (head)每次向后移动两个节点。你可以想象成两个人在跑步一个人快指针的速度是另一个人慢指针的两倍。当跑得快的人到达终点时跑得慢的人恰好就在路程的中间位置。代码逻辑解析虽然你提供的代码片段不完整但其核心部分清晰地展示了算法的执行流程初始化slow 和 head在此处充当快指针都从链表的头节点开始。循环移动在一个循环中循环条件通常是快指针 head 及其下一个节点 head.next 不为空两个指针同时移动。slow slow.next; // 慢指针走一步head head.next.next; // 快指针走两步返回结果当快指针 head 到达链表末尾时循环结束。此时慢指针 slow 所指向的节点就是链表的中间节点。举例说明奇数个节点1 - 2 - 3 - 4 - 5初始slow 指向 1head 指向 1。第一次移动后slow 指向 2head 指向 3。第二次移动后slow 指向 3head 指向 5。head 无法再走两步循环结束。slow 指向的 3 就是中间节点。偶数个节点1 - 2 - 3 - 4 - 5 - 6初始slow 指向 1head 指向 1。第一次移动后slow 指向 2head 指向 3。第二次移动后slow 指向 3head 指向 5。第三次移动后slow 指向 4head 指向 null (越过了 6)。循环结束。slow 指向的 4 就是第二个中间节点。这种算法非常高效只需要遍历一次链表。时间复杂度为 O(n)空间复杂度为 O(1)

更多文章