876. 链表的中间结点
题目描述
输入单链表的头节点 head，链表用数组形式表示，例如 [1,2,3]。
返回链表正中间的那个节点。如果节点数为偶数，中间有两个节点，返回靠后的那一个。
结果以从该节点开始到链表末尾的数组形式展示。
示例 1
输入：head = [1,2,3,4,5] 输出：[3,4,5]
解释：5 个节点，中间是值为 3 的节点。
示例 2
输入：head = [1,2,3,4,5,6] 输出：[4,5,6]
解释：6 个节点，中间的两个是 3 和 4，返回后一个 4。
数据范围
- 节点数在
[1, 100]范围内。 1 <= Node.val <= 100
解题思路
快慢指针。slow 和 fast 都从 head 出发，每轮 slow 走 1 步、fast 走 2 步。fast 没法再走两步（fast 为 None 或 fast.next 为 None）时停下，此时 slow 正好在中间。
为什么正确
每轮结束时，fast 的下标恰好是 slow 下标的 2 倍。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
循环条件写成 fast.next and fast.next.next 时，偶数个节点会停在第一个中间结点，与题目要求的“第二个”不符。条件要写成 fast and fast.next。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowclass Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}var middleNode = function(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};function middleNode(head: ListNode | null): ListNode | null {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
}
return slow;
}