GESP 六级 · GESP 202406 C++ 六级 第 21 题

$n$ 个节点的双向循环链表，在其中查找某个节点的平均时间复杂度是 $O(\log n)$。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】链表遍历｜时间复杂度分析｜数据结构特性

【考纲定位】 本題考《GESP 考綱》數據結構「鏈表」章節，明確指出「鏈表中查找某個節點的時間複雜度是 O(n)」。命題人故意混淆陣列二進制查找 O(log n) 與鏈表線性遍歷 O(n)，卡住考生對抽象數據結構存取特性的理解。

【解题思维】 看到「鏈表」二字先鎖定線性存取特性：無隨機訪問能力，遍歷必須從頭結點開始，順著指針逐一找，平均要檢查 n/2 個節點，複雜度 O(n)。若題目改成「陣列」或「二叉查找樹」，答案才可能 O(log n)，這道題的「平均」二字是干扰詞，實則考最壞情況下的遍歷代價。

【陷阱拆解】 選項 A 誘導考生誤以為鏈表也能二分查找；選項 B 正確，因為鏈表遍歷只能從頭開始，平均時間是 O(n)。許多考生被「循環雙向」這四個字迷惑，誤以為有「跳躍」能力，其實雙向鏈表只是多了一個反向指針，不改變線性遍歷本質。

【反命题思维】 若將「鏈表」換成「有序陣列」，答案瞬間變成 A；若要求「在鏈表中查找第 k 個節點」，答案仍是 O(1)（已知 k），但「查找某個值」必為 O(n)。