0876. 链表的中间结点 #
- 标签:链表、双指针
- 难度:简单
题目大意 #
描述:给定一个单链表的头节点 head
。
要求:返回链表的中间节点。如果有两个中间节点,则返回第二个中间节点。
说明:
- 给定链表的结点数介于
1
和100
之间。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:单指针 #
先遍历一遍链表,统计一下节点个数为 n
,再遍历到 n / 2
的位置,返回中间节点。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
思路 2:快慢指针 #
使用步长不一致的快慢指针进行一次遍历找到链表的中间节点。具体做法如下:
- 使用两个指针
slow
、fast
。slow
、fast
都指向链表的头节点。 - 在循环体中将快、慢指针同时向右移动。其中慢指针每次移动
1
步,即slow = slow.next
。快指针每次移动2
步,即fast = fast.next.next
。 - 等到快指针移动到链表尾部(即
fast == Node
)时跳出循环体,此时slow
指向链表中间位置。 - 返回
slow
指针。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。