109. Convert Sorted List to Binary Search Tree

Link

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Solution

一樣是找一半，透過fast 是slow的兩倍去找到中間的點。

比較ticky的點是要記住slow之前的node，把他的next換成null。這樣recursive時可以自己設定上界。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return new TreeNode(head.val);

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

T: O(n logn)

Time Complexity: The recursive part is O(N), find the mid index need O(logN)

So the total Time Complexity is O(NlogN). Space Complexity: O(logN)