在本教程中，我们将看到如何将Sorted LinkedList转换为平衡二进制搜索树。

有两种方法可以做到这一点。

解决方案1：

将排序数组转换为BST非常相似。
查找链接列表的中间元素，并使其root并递归地进行。
时间复杂性：o(nlogn)。

解决方案2：

该解决方案将遵循自下而上的方法而不是自上而下。

• 我们需要查找链接的长度
• 我们将首先使用N/2节点递归地创建左子树。
• 我们将创建根节点并将左子树连接到根节点。
• 同样创建正确的子树递归，并将根部连接到右子树。

Java程序将Sorted LinkedList转换为Balancy BST：

package org.arpit.theitroad;
 
import org.arpit.theitroad.BinarySearchTreeMain.TreeNode;
 
public class SortedLinkedListToBSTMain {
 
 private Node head;
 
 private static class Node {
 private int value;
 private Node next;
 
 Node(int value) {
 this.value = value;
 
 }
 }
 
 public static class TreeNode {
 int data;
 TreeNode left;
 TreeNode right;
 
 TreeNode(int data) {
 this.data = data;
 }
 }
 
 public static void preOrder(TreeNode root) {
 if (root == null)
 return;
 System.out.print(root.data + " ");
 preOrder(root.left);
 preOrder(root.right);
 }
 
 public void addToTheLast(Node node) {
 
 if (head == null) {
 head = node;
 } else {
 Node temp = head;
 while (temp.next != null)
 temp = temp.next;
 
 temp.next = node;
 }
 }
 
 public void printList(Node head) {
 Node temp = head;
 while (temp != null) {
 System.out.format("%d ", temp.value);
 temp = temp.next;
 }
 System.out.println();
 }
 
 //Find length of linked list using iterative method
 public int lengthOfLinkedList()
 {
 Node temp=head;
 int count = 0;
 while(temp!=null)
 {
 temp=temp.next;
 count++; 
 }
 return count;
 }
 
 public TreeNode convertSortedLinkedListToBST(int n)
 {
 /* Base Case for recursion*/
 if (n <= 0) 
 return null;
 
 /* Recursively creating the left subtree */
 TreeNode left = convertSortedLinkedListToBST(n/2);
 
 /* Create a root node*/
 TreeNode root = new TreeNode(head.value);
 
 //Set pointer to left subtree
 root.left = left;
 head = head.next;
 /* Create right subtree with remaining nodes*/
 root.right = convertSortedLinkedListToBST(n - n/2 - 1);
 
 return root;
 }
 public static void main(String[] args) {
 SortedLinkedListToBSTMain list = new SortedLinkedListToBSTMain();
 //Creating a linked list
 Node head = new Node(10);
 list.addToTheLast(head);
 list.addToTheLast(new Node(20));
 list.addToTheLast(new Node(30));
 list.addToTheLast(new Node(40));
 list.addToTheLast(new Node(50));
 list.addToTheLast(new Node(60));
 list.addToTheLast(new Node(70));
 list.addToTheLast(new Node(80));
 list.addToTheLast(new Node(90));
 System.out.println("Printing linked list :");
 list.printList(head);
 int n =list.lengthOfLinkedList();
 
 TreeNode bst=list.convertSortedLinkedListToBST(n);
 System.out.println("---------------");
 System.out.println("Pre order traversal of binary search tree :");
 preOrder(bst);
 
 }
 
}

运行上面的程序时，我们将得到以下输出：

Printing linked list :
10 20 30 40 50 60 70 80 90 
--------------
Pre order traversal of binary search tree :
50 30 20 10 40 80 70 60 90

时间复杂性：o(n)。