Convert Sorted List to Binary Search Tree (LeetCode Linked List)

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

Idea: This idea comes from tree in order traversal. The in order traversal of the tree is the same as scanning the linked list from head to tail. So we first calculate the length of the linked list, assume it is denoted as n. Then we construct a BST with size n but with all values 0. Finally we in order traversal the BST and scan the linked list simultaneously and assign the corresponding value to the tree node. The only trick is their sequences are completely the same.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   ListNode cur;  
   public TreeNode sortedListToBST(ListNode head) {  
     cur=head;  
     return generate(getLength(head));  
   }  
   public TreeNode generate(int n)  
   {  
     if(n==0)  
       return null;  
     TreeNode node=new TreeNode(0);  
     node.left=generate(n/2);  
     node.val=cur.val;  
     cur=cur.next;  
     node.right=generate(n-n/2-1);  
     return node;  
   }  
   public int getLength(ListNode head)  
   {  
     int counter=0;  
     while(head!=null)  
     {  
       counter+=1;  
       head=head.next;  
     }  
     return counter;  
   }  
 }