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

解题思路

这道题有两种经典解法：

解法一：两次遍历 首先遍历一遍链表计算长度，然后再遍历到第 ⌊n/2⌋ + 1 个节点（从1开始计数）。这种方法思路直观但需要两次遍历。

解法二：快慢指针（推荐） 使用快慢指针的经典技巧。设置两个指针：

  • 快指针每次移动两步
  • 慢指针每次移动一步

当快指针到达链表末尾时，慢指针恰好位于链表中间。这种方法只需要一次遍历，是更优雅的解决方案。

具体实现：快指针从头开始，每次走两步；慢指针也从头开始，每次走一步。当快指针走到末尾（fast == null 或 fast.next == null）时，慢指针所指向的节点就是中间节点。

对于偶数长度的链表，这种方法自然返回第二个中间节点，正好满足题目要求。

代码实现

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
};

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 slow

public class Solution {
    public ListNode MiddleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}

var middleNode = function(head) {
    let slow = head;
    let fast = head;
    
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
快慢指针O(n)O(1)
两次遍历O(n)O(1)

其中 n 为链表长度。快慢指针解法只需要一次遍历，是更优的解决方案。

相关题目