109. Convert Sorted List to Binary Search Tree Leetcode Java

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
A simple solution is use an extra array to store all the value of the linked list and perform the same algorithm of the previous problem: Convert Sorted Array to Binary Search Tree

Another solution is use walker and runner pointers to find the middle element and divide the list half each time and recursively construct the left subtree and right subtree with each half of the list.
Time complexity: O(nlogn) just like merge sort.

  public TreeNode sortedListToBST(ListNode head) {  
    return helper(head,null);  
   }  
   public TreeNode helper(ListNode head,ListNode tail){  
     if(head==tail) return null;  
     ListNode walker=head;  
     ListNode runner=head;  
     while(runner!=tail && runner.next!=tail){  
       walker=walker.next;  
       runner=runner.next.next;  
     }  
     TreeNode root=new TreeNode(walker.val);  
     root.left=helper(head,walker);  
     root.right=helper(walker.next,tail);  
     return root;  
   }  

Another solution is use inorder-traversal to construct the Tree. Basically, we can assume the linked list is divided by three parts l->m-1; m; m+1->r , And we can recursively construct the left subtree , root, right subtree using in-order traversal, leftmost node's value will be the value of first listnode. Each time we build a TreeNode, we can "increment" the listnode, I use an array wrapper to mutate the Listnode during the recursion.
Time complexity: O(n) in-order traversal. 

  public TreeNode sortedListToBST(ListNode head) {  
     int count=0;  
     ListNode cur=head;  
     while(cur!=null){  
       count++;  
       cur=cur.next;  
     }  
     ListNode[] curWrap=new ListNode[1];  
     curWrap[0]=head;  
     return helper(curWrap,0,count-1);  
   }  
   public TreeNode helper(ListNode[] curWrap,int l, int r){  
     if(l>r) return null;  
     int m=(r-l)/2+l;  
     TreeNode leftChild=helper(curWrap,l,m-1);  
     TreeNode root=new TreeNode(curWrap[0].val);  
     root.left=leftChild;  
     curWrap[0]=curWrap[0].next;  
     TreeNode rightChild=helper(curWrap,m+1,r);  
     root.right=rightChild;  
     return root;  
   }