109. Convert Sorted List to Binary Search Tree

Problem:

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

5/31/2018 update:
Making tail exclusive is very genius. Then no need to worry about what's before slow.
--------------------------------------------------------------------------------------------------------------------------
4/26/2018 update:
Find list's mid, sign mid val to current node. Leave left part to left child node and right part to right child node.

To get mid, there are two ways of initializing slow and fast. The difference lies in whether slow is on left or right after finishing when the number of nodes in list is even. Both start from head, slow on right, otherwise on left.

In this problem, slow has on right, because the tail is exclusive.

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

Analysis:
Binary search approach is trivial, O(nlogn).  Use bottom-up approach: O(n).

Solution:

 /**  
  * 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; }  
  * }  
  */  
 class Solution {  
   ListNode list;  
      public TreeNode sortedListToBST(ListNode head) {  
     int size = 0;  
           ListNode runner = head;  
           while (runner != null) {  
                runner = runner.next;  
                size++;  
           }  
     list = head;  
           return helper(0, size - 1);  
   }  
      private TreeNode helper(int low, int high) {  
           if (low > high) return null;  
     int mid = (low + high ) /2;  
           TreeNode left = helper(low, mid - 1);  
           TreeNode parent = new TreeNode(list.val);  
     parent.left = left;  
           list = list.next;  
           parent.right = helper(mid + 1, high);  
           return parent;  
      }  
 }