[LeetCode] Convert Sorted List to Binary Search Tree

Total Accepted: 9476 Total Submissions: 35578

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        
        int len = 0;
        ListNode lo = head;
        ListNode hi, mid;
        
        // get length of list
        while (lo != null) {
            len++;
            lo = lo.next;
        }
        
        // get the middle index
        int midIndex = (len >> 1) - 1;
        lo = head;
        while (midIndex-- > 0) lo = lo.next;
        
        //  divide original list into 3 parts
        mid = lo.next;
        hi = mid.next;
        lo.next = null;
        
        // build BST recursively
        TreeNode root = new TreeNode(mid.val);
        root.left   = sortedListToBST(head);
        root.right  = sortedListToBST(hi);
        
        return root;
    }

}
           

// use a end flag
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return getBST(head, null);
    }
    
    public TreeNode getBST(ListNode start, ListNode endFlag) {
        if (start == endFlag) return null;
        
        ListNode hi = start;
        ListNode mid = start;
        
        // get mid node with 2 pointers
        while (hi != endFlag && hi.next != endFlag) {
            mid = mid.next;
            hi = hi.next.next;
        }
        
        TreeNode root = new TreeNode(mid.val);
        root.left   = getBST(start, mid);
        root.right  = getBST(mid.next, endFlag);
        
        return root;
    }

}