LeetCode 876. 链表的中间结点
题目描述
思路分析
- 使用快慢指针法。
- 初始化两个指针 slow 和 fast，均指向链表的头节点。
- 快指针 fast 每次移动两个节点，慢指针 slow 每次移动一个节点。
- 当快指针 fast 到达链表末尾时，慢指针 slow 所指向的节点即为链表的中间节点。
参考代码
1
2
3
4
5
6
7
8
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
- 时间复杂度: O (n)，其中 n 是链表的长度。我们只需要遍历链表一次。
- 空间复杂度: O (1)，我们只使用了常数级别的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！