Description
給定一個單向鏈結串列的頭節點
head，回傳鏈結串列的中間節點。若有兩個中間節點，回傳第二個。
Example:
Input: head = [1,2,3,4,5] Output: [3,4,5]
Intuition#
核心思路：快慢指針，快指針走兩步、慢指針走一步，快指針到底時慢指針剛好在中間。
- 不知道鏈結串列長度，無法直接算出中間位置
- 快慢指針：fast 每次走 2 步，slow 每次走 1 步，fast 到終點時 slow 正好在中間
- 兩次遍歷法：先算長度再走到中間，但不如快慢指針優雅
Approaches#
1: Two Pass (Count Length)#
- 概念: 第一次遍歷計算長度，第二次走到 length / 2 的位置
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun middleNode(head: ListNode?): ListNode? {
var length = 0
var curr = head
while (curr != null) {
length++
curr = curr.next
}
curr = head
for (i in 0 until length / 2) {
curr = curr?.next
}
return curr
}
}⭐2: Fast-Slow Pointer#
- 概念: 快指針走兩步、慢指針走一步，一次遍歷找到中間節點
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun middleNode(head: ListNode?): ListNode? {
var slow = head
var fast = head
while (fast?.next != null) {
slow = slow?.next
fast = fast.next?.next
}
return slow
}
}🔑 Takeaways#
- Pattern: 快慢指針是尋找鏈結串列中點的標準技巧，也用於環偵測、回文判斷等
- 關鍵技巧: 迴圈條件
fast?.next != null確保偶數長度時回傳第二個中間節點