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; }
}
**/
/**
Definition for a binary tree node.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
**/
public class Solution {
  public TreeNode sortedListToBST(ListNode head) {
      
  }
}

This problem is selected from LeetCode.

Solution

Solution1: The basic idea is to find the middle node of the list which is the root of the BST. Then use the same method recursively
to find the root of the left sub-tree and the root of the right sub-tree. Here, we pass a head and a tail pointer to the recursion
call to divide the list.

In each recursion call, to find the middle point of the list part, setup a fast pointer and a slow pointer to traverse the list
part. Each time, the fast pointer steps two nodes and the slow pointer steps one node. When the fast pointer reaches the tail, the slow
pointer is at the middle of the list part.

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

This solution scans all the n nodes to get the root (the middle node) in the list. Then it searches the roots of the left sub-tree
and right sub-tree by scanning the first half (n/2 nodes) of the list and the second half (n/2 nodes) of the list. Therefore, to
get the second level of the BST, it searches n/2 + n/2 = n nodes again.

Basically, to get the nodes of each level in the BST, the solution searches n nodes. There are log(n) levels in the BST,
so in total, it searches the nodes O(n*lon(n)) times. In other words, the time complexity of solution1 is O(nlog(n)).

Solution2: There’s another magic solution that only takes O(n) runtime. Instead of building the BST from top to bottom like solution1,
this solution builds the BST from bottom to top.

public class Solution {
  private ListNode current;
  
  public TreeNode sortedListToBST(ListNode head) {
    if(head == null) return null;

    int size = 0;
    ListNode runner = head;
    current = head;

    while(runner != null){
      runner = runner.next;
      size ++;
    }

    return sortedListToBST(0, size - 1);
  }
  
  public TreeNode sortedListToBST(int start, int end){
    if(start > end) return null;

    int mid = start + (end - start) / 2;
    TreeNode left = sortedListToBST(start, mid - 1);

    TreeNode treenode = new TreeNode(current.val);
    treenode.left = left;
    current = current.next;

    TreeNode right = sortedListToBST(mid + 1, end);
    treenode.right = right;

    return treenode;
  }
}

RelatedPost