[LeetCode] 109. Convert Sorted List to Binary Search Tree

轉自LeetCode

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
<Solution>

這題和 Convert Sorted Array to Binary Search Tree 一樣

只是資料結構變成 linked list，所以在操作上會不同

先看 recursive 的解法

想法也是一樣，找到中間的node，然後左半部是左子樹，右半部是右子樹

用 recursive 方式把樹建出來

那 linked list 怎麼找到中間的node，利用兩個指針來達到

fast 指針一次移動兩個 node，slow指針一次移動一個 node

這樣當 fast 移動了 n 個 node 的時候，slow 只移動了 n/2，這樣就可以找到中間的node了

找到中間的node之後，再切出左半部和右半部，並 recursive 做下去即可

code 如下

那一樣有 iterative 的解法，想法也是和 Convert Sorted Array to Binary Search Tree 一樣

用一個 queue 來存放要處理的 list，以及相對應的 tree node

每個循環，找到 list 中間的 node，將數值更新到對應的 tree node

然後再分左半部和右半部，繼續循環下去

code 如下