# 109. Convert Sorted List to Binary Search Tree ⭐

Medium
Given the `head` of 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 1:
Input: head = [-10,-3,0,5,9]
Output:
[0,-3,9,-10,null,5]
Explanation:
One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
Example 2:
Input: head = []
Output:
[]
Constraints:
• The number of nodes in `head` is in the range `[0, 2 * 104]`.
• `-105 <= Node.val <= 105`

### 解題

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedListToBST(head *ListNode) *TreeNode {
if head==nil { return nil }
if head.Next == nil {
return &TreeNode{ Val: head.Val, Left:nil, Right: nil }
}
var prev *ListNode
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil
root := &TreeNode{ Val: slow.Val}
root.Right = sortedListToBST(slow.Next)
return root
}

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedListToBST(head *ListNode) *TreeNode {
if head==nil { return nil }
if head.Next == nil {
return &TreeNode{ Val: head.Val, Left:nil, Right: nil }
}
nodes := make([]int, 0)
for head != nil {
nodes = append(nodes, head.Val)
}
return helper(nodes)
}
func helper(nodes []int) *TreeNode {
l := len(nodes)
if l == 0 { return nil }
if l == 1 { return &TreeNode{ Val: nodes[0], Left:nil, Right: nil } }
mid := l / 2
return &TreeNode{
Val: nodes[mid],
Left: helper(nodes[0:mid]),
Right: helper(nodes[mid+1:]),
}
}