876. 链表的中间结点

题目

给你单链表的头结点 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

解答

思路

用两个指针分别指向头节点，每次循环：

• slow 走一步
• fast 走两步

当链表长度为奇数时，slow 走了 $k$ 步时，此时位于第 $k+1$ 个节点上，此时 fast 走了 $2k$ 步，位于 $2k+1=n$ 个节点上，刚好是尾节点，因此 slow 对应的就是中间节点。

当链表长度为偶数时，slow 走了 $k$ 步时，此时位于第 $k+1$ 个节点上，此时 fast 走了 $2k$ 步，位于 $2k+1$ 个节点上，由于 $n=2k$，因此中间的两个节点分别是 $k,k+1$，此时 slow 对应的就是中间两个节点的 第二个节点。

• 奇数长度退出循环时，fast.next = None
• 偶数长度退出循环时，fast = None

复杂度：

• 时间复杂度为 $O(n)$
• 空间复杂度为 $O(1)$

代码

C++ 代码

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        auto slow = head;
        auto fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

Python 代码

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow