1、題目描述

給你單鏈表的頭結點?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

2、解題思路--快慢指針

使用快慢指針（Fast-Slow Pointer）來找到鏈表的中間節點：

• 快指針（fast）：每次移動?兩步（fast = fast.next.next）。

• 慢指針（slow）：每次移動?一步（slow = slow.next）。

當快指針到達鏈表末尾時，慢指針正好指向鏈表的中間節點。

關鍵點

1. 循環條件：

   • while (fast != null && fast.next != null)

     • fast != null：確保快指針沒有越界（適用于奇數長度鏈表）。

     • fast.next != null：確保快指針可以移動兩步（適用于偶數長度鏈表）。

2. 奇數長度鏈表：

   • 鏈表長度為奇數時，快指針最終會指向最后一個節點（fast.next == null），此時慢指針正好指向中間節點。

   • 例如：1 -> 2 -> 3 -> 4 -> 5，慢指針指向?3。

3. 偶數長度鏈表：

   • 鏈表長度為偶數時，快指針最終會指向?null（因為?fast.next.next?會越界），此時慢指針指向第二個中間節點（題目通常要求返回第二個中間節點）。

   • 例如：1 -> 2 -> 3 -> 4，慢指針指向?3（第二個中間節點）。

public static ListNode middleNode(ListNode head) {ListNode fast = head, slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;  // 快指針每次走兩步slow = slow.next;       // 慢指針每次走一步}return slow;  // 慢指針指向中間節點
}

時間復雜度

• O(n)，其中?n?是鏈表的長度。

• 快指針遍歷鏈表約?n/2?次，慢指針移動?n/2?次，因此總的時間復雜度是線性的。