0876. 链表的中间结点 #
- 标签:链表、指针
- 难度:简单
题目大意 #
给定一个单链表,返回链表的中间节点。如果有两个中间节点,则返回第二个中间节点。
解题思路 #
1. 单指针遍历 #
先遍历一遍链表,统计一下节点个数为 n,再遍历到 n / 2 的位置,返回中间节点。
2. 快慢指针 #
常规思路是:先遍历一遍链表,统计一下节点个数为 n
,再遍历到 n / 2
的位置,返回中间节点。
我们也可以使用步长不一致的快慢指针进行一次遍历找到链表的中间节点。具体做法如下:
- 使用两个指针
slow
、fast
。slow
、fast
都指向链表的头节点。 - 在循环体中将快、慢指针同时向右移动。其中慢指针每次移动
1
步,即slow = slow.next
。快指针每次移动2
步,即fast = fast.next.next
。 - 等到快指针移动到链表尾部(即
fast == Node
)时跳出循环体,此时slow
指向链表中间位置。 - 返回
slow
指针。
代码 #
- 单指针遍历
|
|
- 快慢指针
|
|