Convert Sorted List to Binary Search Tree

leetcode 109

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

Solution. At the beginning, I came up idea to use slow and fast point to find the middle element, and generate node. And recursively do left and right side. But this takes O(nlogn) time.

// O(nlogn) solution
public static TreeNode sortedListToBST2(ListNode head) {
    if (head == null) {
        return null;
    }
    if (head.next == null) {
        return new TreeNode(head.val);
    }
    ListNode slow = head, fast = head.next; // pivot should be slow.next. In this way, it is easy to set slow.next = null
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    TreeNode node = new TreeNode(slow.next.val);    // pivot is slow.next
    ListNode next = slow.next.next;
    slow.next = null; // cut the list.
    node.left = sortedListToBST2(head);
    node.right = sortedListToBST2(next);
    return node;
}

However, there is a better O(n) solution. First, count the number of ListNode. And build the AVL tree based on the number.

For 1, 2, 3, 4, 5, 6. mid = 4, left = [1, 2, 3], right = [5, 6]
For 1, 2, 3, 4, 5, 6, 7. mid = 4, left = [1, 2, 3], right = [5, 6, 7]

The code is like below:

// O(n) time, O(logN) solution.
// count number of ListNode, then divide n into 3 parts. And recursively build the AVL tree
// for 1, 2, 3, 4, 5, 6. mid = 4, left = [1, 2, 3], right = [5, 6]
// for 1, 2, 3, 4, 5, 6, 7. mid = 4, left = [1, 2, 3], right = [5, 6, 7]
private ListNode head = null;

public TreeNode sortedListToBST(ListNode head) {
    this.head = head;
    int n = 0;
    ListNode node = head;
    while (node != null) {
        n++;
        node = node.next;
    }
    return helper(n);
}

private TreeNode helper(int n) {
    if (n <= 0) {
        return null;
    }
    int mid = n >> 1;
    TreeNode left = helper(mid);    // left part
    TreeNode node = new TreeNode(head.val);
    head = head.next;
    node.left = left;
    node.right = helper(n - mid - 1);   // right part
    return node;
}

Check my code on github.