Swift 数据结构和算法(28) + Leetcode876. 链表的间结点(双指针)
概念
使用场景与应用
核心概念:
-
快慢指针技巧:通过设置两个指针,一个以较快的速度移动(例如每次两步),另一个以较慢的速度移动(例如每次一步),这种方法可以帮助我们高效地解决一些链表问题。
-
时间与空间效率:这种方法只需要遍历链表一次,所以时间复杂度为 (O(n))。由于我们只使用了固定数量的额外空间(两个指针),空间复杂度为 (O(1))。
实际应用:
-
分割数据流:在处理大型数据流时,如在网络通信或大型数据处理中,有时我们需要分割数据或找到数据的中点。快慢指针技巧可以帮助我们在单次遍历中找到数据流的中点。
技术点:使用两个指针以不同的速度遍历数据流,当快指针到达数据流的尾部时,慢指针正好在数据流的中间。
-
循环检测:在计算机程序中,有时我们需要检测一个序列是否存在循环。例如,我们可能需要确定一个随机数生成器是否进入了一个周期性的模式。
技术点:使用快慢指针遍历序列。如果存在循环,快慢指针最终会相遇。
-
音频或视频处理:在处理音频或视频流时,有时我们需要快速找到流的中间部分以进行编辑或分析。
技术点:使用快慢指针同时处理数据流。当快指针到达流的尾部时,慢指针将在流的中间。
总之,快慢指针技巧是一个非常实用的工具,它在许多实际场景中都有应用,特别是当我们需要在单次遍历中获取数据的中间点或检测循环时。
错误与反思
要代入测试用例去看看
// if fast == nil {
// slow = slow?.next
// }
题目
876. 链表的中间结点 给你单链表的头结点 head
,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入: head = [1,2,3,4,5]
输出: [3,4,5]
解释: 链表只有一个中间结点,值为 3 。
示例 2:
输入: head = [1,2,3,4,5,6]
输出: [4,5,6]
解释: 该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。
提示:
- 链表的结点数范围是
[1, 100]
1 <= Node.val <= 100
解题思路🙋🏻 ♀️
边界思考🤔
代码
class Solution {
func middleNode(_ head: ListNode?) -> ListNode? {
if head == nil {
return nil
}
var slow = head
var fast = head
while fast != nil && fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
}
return slow
}
}
时空复杂度分析
O(n)
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgecggk
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01