[leetcode]Convert Sorted List To Binary Search Tree

O(nlogn)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

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

I will update with a O(n) solution if I have time:
http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html
This is a good one,  move along the linkedlist when doing recursion.