LeetCode#109. Convert Sorted List to Binary Search Tree

• 題目：将一個排序後連結清單轉成一個平衡二叉查找樹
• 難度：Medium
• 思路：這題的思路跟将有序數組轉成平衡二叉查找樹一樣，查找一個連結清單的中間元素需要定義兩個指針，fast指針每次移動兩步，slow指針每次移動一步，fast指針移動到連結清單尾部時，slow指向的節點為中間節點
• 代碼：

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null){
            return null;
        }
        return recursion(head, null);
    } 
    public TreeNode recursion(ListNode head, ListNode tail){
        if(head == tail){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != tail && fast.next != tail){
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode node = new TreeNode(slow.val);
        node.left = recursion(head, slow);
        node.right = recursion(slow.next, tail);
        return node;
    }
}