https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

convert-sorted-list-to-binary-search-tree.go

/**
 * 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
    }
    
    middle := split(head)
    root := &TreeNode{
        Val: middle.Val,
    }
    
    if middle != head {
        root.Left = sortedListToBST(head)
        root.Right = sortedListToBST(middle.Next)
    }
    
    return root
}

func split(head *ListNode) *ListNode {
    var prev *ListNode
    hare, tortoise := head, head
    
    for hare != nil && hare.Next != nil {
        prev = tortoise
        hare = hare.Next.Next
        tortoise = tortoise.Next
    }
    
    if prev != nil {
        prev.Next = nil
    }
    
    return tortoise
}