LeetCode 解題筆記：2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

作者：王一哲
日期：2026年8月31日


LeetCode 題目連結：2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

解題想法

中等難度題。題目一個鏈結串列的開頭節點 $head$，如果鏈結串列之中某個節點的值同時大於前、後節點的值，或是同時小於前、後節點的值，這樣的節點稱為關鍵點 (critical point)，鏈結串列頭、尾的節點不會是關鍵點。題目要回傳兩個關鍵點的最小與最大距離，如果只有1個或沒有關鍵點，無法取距離，回傳 $[-1, -1]$。

可以先建立一個節點 $pre$ 指向 $head$，另一個走訪用的虛擬節點 $dummy$ 指向 $head.next$，再用一個 while 迴圈走訪所有的節點，如果還有 $dummy.next$ 繼續執行。再建一個陣列 $pos$ 儲存關鍵點的位置，用變數 $imin$ 儲存最小的距離，$step$ 儲存目前的節點與 $head$ 的距離。每次執行 while 迴圈時，先檢查這個節點的值是否同時大於 $pre$ 或 $dummy.next$ 的值，或是同時小於 $pre$ 或 $dummy.next$ 的值，如果 $pos$ 已經有資料，檢查 $step - pos[-1]$ 是否是新的最小值，再將 $step$ 加入 $pos$。如果最後 $pos$ 長度小於 2，回傳 $[-1, -1]$；反之，回傳 $[imin, pos[-1] - pos[0]]$。

Python 程式碼

Runtime: 65 ms, beats 90.43%. Memory: 63.25 MB, beats 23.68%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        pre = head  # 前一個節點，先指向 head
        dummy = head.next  # 走訪用的虛擬節點，先指向 head.next
        step = 0  # 目前節點與 head 的距離
        pos = []  # 關鍵節點與 head 的距離
        imin = float('inf')  # 最矩距離
        while dummy.next:  # 如果有 dummy.next 繼續執行
            step += 1
            # 檢查 dummy 是否同時比前、後節點小或同時比前、後節點大
            if (pre.val > dummy.val and dummy.next.val > dummy.val) or (pre.val < dummy.val and dummy.next.val < dummy.val):
                if pos: imin = min(imin, step - pos[-1])  # 如果 pos 已經有資料，更新 imin
                pos.append(step)  # 加入 step
            pre = dummy  # pre 指向現在的 dummy
            dummy = dummy.next  # dummy 指向下一格
        
        # 如果關鍵節點不到 2 個，無法取距離，回傳 [-1, -1]
        if len(pos) < 2:
            return [-1, -1]
        else:  # 可以找距離，最遠距離為 pos 兩端
            return [imin, pos[-1] - pos[0]]

C++ 程式碼

Runtime: 6 ms, beats 36.54%. Memory: 128.34 MB, beats 39.79%.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        ListNode* pre = head;  // 前一個節點，先指向 head
        ListNode* dummy = head->next;  // 走訪用的虛擬節點，先指向 head.next
        int step = 0, imin = 100000;  // 目前節點與 head 的距離，關鍵節點最短距離
        vector<int> pos;  // 關鍵節點與 head 的距離
        while(dummy->next != nullptr) {  // 如果有 dummy->next 繼續執行
            step++;
            // 檢查 dummy 是否同時比前、後節點小或同時比前、後節點大
            if ((pre->val > dummy->val && dummy->next->val > dummy->val) || 
                (pre->val < dummy->val && dummy->next->val < dummy->val)) {
                if (!pos.empty() && step - pos.back() < imin) {  // 如果 pos 已經有資料
                    imin = step - pos.back();
                }
                pos.push_back(step);  // 加入 step
            }
            pre = dummy;  // pre 指向現在的 dummy
            dummy = dummy->next;  // dummy 指向下一格
        }
        
        // 輸出答案
        int m = (int)pos.size();
        if (m < 2) {  // 如果關鍵節點不到 2 個，無法取距離，回傳 {-1, -1}
            return {-1, -1};
        } else {  // 可以找距離，最遠距離為 pos 兩端
            return {imin, pos[m-1] - pos[0]};
        }
    }
};