Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save alldroll/026ea611ca29088bb0e9c897cfe90587 to your computer and use it in GitHub Desktop.
Save alldroll/026ea611ca29088bb0e9c897cfe90587 to your computer and use it in GitHub Desktop.
/**
* 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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment