/** * Definition for singly-linked list. public class ListNode { int val;ListNode next; ListNode(int * x) { val = x; } } */ /** * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode * right; TreeNode(int x) { val = x; } } */ class Solution {
privateList<Integer> values;
public Solution() { this.values = new ArrayList<Integer>(); }
private void mapListToValues(ListNode head) { while (head != null) { this.values.add(head.val); head = head.next; } }
private TreeNode convertListToBST(int left, int right) { // Invalid case if (left > right) { return null; }
// Middle element forms the root. int mid = (left + right) / 2; TreeNode node = new TreeNode(this.values.get(mid));
// Base case for when there is only one element left in the array if (left == right) { return node; }
// Recursively form BST on the two halves node.left = convertListToBST(left, mid - 1); node.right = convertListToBST(mid + 1, right); return node; }
public TreeNode sortedListToBST(ListNode head) {
// Form an array out of the given linked list and then // use the array to form the BST. this.mapListToValues(head);
// Convert the array to return convertListToBST(0, this.values.size() - 1); } }
/** * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int * x) { val = x; } } */ /** * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode * right; TreeNode(int x) { val = x; } } */ classSolution {
// The pointer used to disconnect the left half from the mid node. ListNodeprevPtr=null; ListNodeslowPtr= head; ListNodefastPtr= head;
// Iterate until fastPr doesn't reach the end of the linked list. while (fastPtr != null && fastPtr.next != null) { prevPtr = slowPtr; slowPtr = slowPtr.next; fastPtr = fastPtr.next.next; }
// Handling the case when slowPtr was equal to head. if (prevPtr != null) { prevPtr.next = null; }
return slowPtr; }
public TreeNode sortedListToBST(ListNode head) {
// If the head doesn't exist, then the linked list is empty if (head == null) { returnnull; }
// Find the middle element for the list. ListNodemid=this.findMiddleElement(head);
// The mid becomes the root of the BST. TreeNodenode=newTreeNode(mid.val);
// Base case when there is just one element in the linked list if (head == mid) { return node; }
// Recursively form balanced BSTs using the left and right halves of the original list. node.left = this.sortedListToBST(head); node.right = this.sortedListToBST(mid.next); return node; } }