Swift 数据结构和算法(28) + Leetcode876. 链表的间结点(双指针)

概念

使用场景与应用

核心概念：

1. 快慢指针技巧：通过设置两个指针，一个以较快的速度移动（例如每次两步），另一个以较慢的速度移动（例如每次一步），这种方法可以帮助我们高效地解决一些链表问题。

2. 时间与空间效率：这种方法只需要遍历链表一次，所以时间复杂度为 (O(n))。由于我们只使用了固定数量的额外空间（两个指针），空间复杂度为 (O(1))。

实际应用：

1. 分割数据流：在处理大型数据流时，如在网络通信或大型数据处理中，有时我们需要分割数据或找到数据的中点。快慢指针技巧可以帮助我们在单次遍历中找到数据流的中点。

   技术点：使用两个指针以不同的速度遍历数据流，当快指针到达数据流的尾部时，慢指针正好在数据流的中间。

2. 循环检测：在计算机程序中，有时我们需要检测一个序列是否存在循环。例如，我们可能需要确定一个随机数生成器是否进入了一个周期性的模式。

   技术点：使用快慢指针遍历序列。如果存在循环，快慢指针最终会相遇。

3. 音频或视频处理：在处理音频或视频流时，有时我们需要快速找到流的中间部分以进行编辑或分析。

   技术点：使用快慢指针同时处理数据流。当快指针到达流的尾部时，慢指针将在流的中间。

总之，快慢指针技巧是一个非常实用的工具，它在许多实际场景中都有应用，特别是当我们需要在单次遍历中获取数据的中间点或检测循环时。

错误与反思

要代入测试用例去看看

//        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)

这篇好文章是转载于：学新通技术网