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;
}
}
}