leetcode109.Convert Sorted List to Binary Search Tree

题目要求

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

给一个按照递增顺序排列的链表。将该链表转化为平衡二叉树。

思路和代码

在这里需要注意的是，因为提供的数据结构为链表，所以我们必须顺序遍历才能知道该链表的长度以及该链表的中间位置。在这里，我们可以采用递归的形式，而且在递归中我们通过双指针的方式找到其中的中间节点。并依次递归左子节点和右子节点。

public TreeNode sortedListToBST(ListNode head) {
    if(head==null) return null;
    return sortedListToBST(head, null);
}

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