难度: Easy
给你单链表的头结点 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
Submission
运行时间: 32 ms
内存: 14.9 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
Explain
这个题解使用了快慢指针的思路。初始时，快指针 fast 和慢指针 slow 都指向链表的头节点。快指针 fast 每次走两步，慢指针 slow 每次走一步。当快指针到达链表尾部时，慢指针正好到达链表的中间节点。通过这种方式，只需要遍历一次链表就可以找到中间节点。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
fast = slow = head
# 快指针 fast 每次走两步，慢指针 slow 每次走一步
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# 当 fast 到达链表尾部时，slow 正好在中间节点
return slow
Explore
在链表有偶数个节点时，快指针每次移动两步，慢指针每次移动一步。由于快指针的移动速度是慢指针的两倍，当快指针达到链表的末尾（fast.next为None）时，慢指针会停在中间两个节点的第二个。这是因为在每个循环中，慢指针在快指针完成其两步移动之后才移动一步。因此，在快指针到达链表末端时，慢指针自然会位于第二个中间节点。
如果链表只有一个节点，快慢指针初始都指向这个唯一的节点。在算法的开始，快指针试图移动两步，但由于没有下一个节点（fast.next为None），循环终止。此时，慢指针仍然指向头节点，即这个唯一的节点。因此，算法返回这个节点作为中间节点，这是正确的行为。
在快指针移动前检查`fast`和`fast.next`是否为`None`是为了确保在访问`fast.next.next`时不会遇到`NoneType`对象没有`next`属性的错误（即避免访问空指针）。这种检查是必要的，因为如果快指针或其下一个节点是`None`，那么尝试访问`fast.next.next`将导致程序出错。通过这种方式，我们确保只有当快指针有有效的后续节点时，它才会尝试进一步移动。
快慢指针方法在处理大规模数据时，性能表现为O(n)，因为无论如何都需要遍历链表一次以找到中间节点。这种算法已经是线性时间复杂度，是找到链表中间节点的最优解。对于进一步的优化，由于每个节点都需要被访问以确定链表的长度，实际上没有办法降低算法的时间复杂度。然而，优化可以从其他角度入手，例如改进内存使用或实现细节，以适应特定的应用场景或环境。