Convert Sorted List to Balanced BST

Source

• lintcode: Convert Sorted List to Balanced BST

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

Example
               2
1->2->3  =>   / \
             1   3

Java

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    public TreeNode sortedListToBST(ListNode head) {  
        if(head==null) return null;
        if(head.next==null) return new TreeNode(head.val);

        ListNode slow=head;
        ListNode fast=head;
        ListNode tmp = null;

        while(fast!=null && fast.next!=null){
            tmp=slow;
            slow=slow.next;
            fast=fast.next.next;
        }

        //tmp不可能为null
        //因为tmp为null的情况只能是head.next==null但是这种情况已经在最开始返回了
        tmp.next=null;

        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}