876. 链表的中间结点

题目链接：876. 链表的中间结点

题目描述

给定一个头结点为 head 的非空单向链表，请返回链表的中间结点。如果链表有两个中间结点（即链表长度为偶数的情况），则返回第二个中间结点。

核心思考：快慢指针

对于单向链表，寻找中间节点的经典且高效的做法是使用快慢双指针（Fast and Slow Pointers）。由于单向链表无法直接获取总长度，使用双指针可以在一次遍历内解决寻找中点的问题。

核心逻辑在于利用两个步长不同的指针来同时遍历链表：

1. 初始化：定义两个指针 slow 和 fast，并将它们均指向链表的头节点 head。
2. 指针偏移：在遍历过程中，慢指针 slow 每次向前移动 1 个节点，而快指针 fast 每次向前移动 2 个节点。
3. 定位中点：由于快指针的移动速度严格等同于慢指针的两倍，因此，当快指针遍历完整个链表并到达边界时，慢指针所走过的距离恰好等于链表总长度的一半。此时 slow 指针指向的位置即为链表的中间节点。

边界条件：链表长度的奇偶分析

针对链表总节点数为奇数或偶数的情况，快指针结束遍历的具体边界表现会有所不同，我们需要通过这两个状态来构建完善的 while 循环终止条件：

• 针对节点数为奇数的链表：快指针 fast 最终会停留在链表的最后一个尾节点，此时满足 fast.next == None。由于除以 2 的操作刚好停在正中，此时慢指针 slow 严丝合缝地停留在链表的唯一正中心节点上。
• 针对节点数为偶数的链表：快指针 fast 最终会越过链表的尾节点，指向空指针，此时满足 fast == None。由于题干规定“若是双中心节点，则返回第二个”，在此状态下，慢指针 slow 也会多走半步，完美指向两个中心节点的右侧那个。

综合上述两种场景，无论链表长度奇偶，只要保证快指针本身不为空，且其下一步有节点可跳，就可以继续迭代。因此循环条件统一收敛为：while fast is not None and fast.next is not None。

解题思路 (Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 初始化快慢指针，指向头节点
        slow = fast = head
        
        # 只要 fast 以及 fast.next 都不为空，说明还可以继续向前以 2 的步长跳跃
        while fast is not None and fast.next is not None:
            # 慢指针走一步
            slow = slow.next
            # 快指针走两步
            fast = fast.next.next
            
        # 循环结束时，慢指针刚好到达中间节点
        return slow

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是链表的节点数量。快指针每次跨越两个节点，因此循环体内的执行次数约为 $N/2$，整体代价是线性的。
• 空间复杂度：$O(1)$。算法仅在内存中额外声明了 slow 和 fast 两个常数级别的指针变量，未使用任何额外的动态数据结构空间。