Question

Formatted question description: https://leetcode.ca/all/109.html

109	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.

@tag-linkedlist

Algorithm

The idea is exactly the same as the previous Convert Sorted Array to Binary Search Tree, except that the data types of operations are different, one is an array and the other is a linked list. Arrays are convenient because you can directly access any element through index, but linked lists cannot. Because the binary search method needs to find the midpoint every time.

After finding the midpoint, we need to establish a root node of the number based on the midpoint value, and then we need to disconnect the original linked list and divide it into two linked lists, neither of which can contain the original midpoint, and then recursively call the two linked lists separately Original function, connected to the left and right child nodes respectively.

Code

Java

public class Convert_Sorted_List_to_Binary_Search_Tree {

	/**
	 * Definition for singly-linked list.
	 * public class ListNode {
	 *     int val;
	 *     ListNode next;
	 *     ListNode(int x) { val = x; next = null; }
	 * }
	 */
	/**
	 * Definition for binary tree
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */
    public class Solution {
        public TreeNode sortedListToBST(ListNode head) {

            if (head == null) {
                return null;
            }
            if (head.next == null) {
                return new TreeNode(head.val);
            }

            // find mid
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode slow = head, fast = head, prev = dummy;
            while (fast != null && fast.next != null) {
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }

            // prev is one before mid
            // ListNode 2ndPartHead = slow.next; // @note@note: illegal, cannot start with number
            ListNode newHead = slow.next;
            prev.next = null; // @note: cut

            TreeNode root = new TreeNode(slow.val);
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(newHead);

            return root;
        }
    }

}

All Problems

All Solutions