Convert Sorted List to Binary Search Tree ใน C++ : แปลง Linked List เรียงเป็น Height-Balanced BST

ให้ **Singly Linked List** เรียงจากน้อยไปมาก แปลงเป็น **Height-Balanced BST** (ความสูง Subtree ทุก Node ต่างกัน ≤ 1)

ตัวอย่าง

List: -10 -> -3 -> 0 -> 5 -> 9

BST (หนึ่งในคำตอบที่เป็นไปได้):
      0
     /  \
   -3    5
   /      \
 -10       9

Inorder: -10 -3 0 5 9 (ตรงกับ List)

แนวทาง: Divide & Conquer + Find Middle (Fast/Slow Pointer)

1. Base Case: List ว่าง -> Return NULL
2. หา **Middle Node** (Slow/Fast Pointer) -> เป็น Root
3. Split List: prev->next = NULL (Left Part), mid->next (Right Part)
4. Recursive Build:
   • root->left = sortedListToBST(leftHead)
   • root->right = sortedListToBST(rightHead)

การหา Middle ทุก Recursive Call ทำให้ Time = O(N log N) (สามารถทำ O(N) ด้วย Inorder Simulation ได้ แต่ Complexity สูงขึ้น)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    // Return {prev_of_mid, mid}
    pair<ListNode*, ListNode*> getMid(ListNode* head) {
        ListNode *prev = NULL, *slow = head, *fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        }
        return {prev, slow};
    }

    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return NULL;

        auto [prev, mid] = getMid(head);
        TreeNode* root = new TreeNode(mid->val);

        ListNode* rightHead = mid->next;
        mid->next = NULL; // Cut left part

        root->right = sortedListToBST(rightHead);

        if (prev) {
            prev->next = NULL; // Cut left part completely
            root->left = sortedListToBST(head);
        }
        return root;
    }
};

Input / Output

Input:  [-10,-3,0,5,9]
Output: -10 -3 0 5 9 (Inorder Traversal of constructed BST)

ความซับซ้อน (Complexity)

• Time: O(N log N) — หา Middle O(N) ต่อ Level, มี log N Levels
• Space: O(log N) — Recursion Stack (Height of BST)

Optimization Note

สามารถทำ **O(N) Time** ได้โดย:

1. หา Length ของ List ก่อน
2. Build BST ด้วย Inorder Traversal Simulation (Left -> Node -> Right) เดิน List Pointer ไปพร้อมๆ กัน