LeetCode Convert Sorted List to BST：鏈表轉數組復用數組解法

題目回顧

有序單鏈表轉高度平衡 BST。

簡單做法：鏈表 → 數組 → 遞歸構建

時間 O(n)，空間 O(n)（數組 + 遞歸棧）。代碼復用 LeetCode 108。

C++ 代碼

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector nums;
        for (ListNode* p = head; p; p = p->next) nums.push_back(p->val);
        return build(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* build(vector& nums, int l, int r) {
        if (l > r) return nullptr;
        int mid = (l + r) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = build(nums, l, mid - 1);
        root->right = build(nums, mid + 1, r);
        return root;
    }
};

進階：O(1) 空間（快慢指針找中點）

不轉數組，直接在鏈表上用快慢指針找中點作為根，斷開左右遞歸。時間 O(n log n)，空間 O(log n) 遞歸棧。面試可作為優化方向討論。