L109. Convert Sorted List to Binary Search Tree

Problem:

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Solution:

• TC NlogN SC logN

• use two pointers to find the mid at linked list

• left would be the head, and right will be mid.next

public TreeNode sortedListToBST(ListNode head) {
    if(head == null) return null;
    ListNode mid = this.findMid(head);
    TreeNode node = new TreeNode(mid.val);
    if(head == mid) return node;
    node.left = this.sortedListToBST(head);
    node.right = this.sortedListToBST(mid.next);
    return node;
}
private ListNode findMid(ListNode head){        
    ListNode pre = null;
    ListNode slow = head;
    ListNode fast = head;
        
    while(fast != null && fast.next != null){
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    if(pre != null){
        pre.next = null;
    }
    return slow;
}