Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.
Note: There might be nodes with the same value.
Example 1:
Input:
Linked List: 1->2->3->4->5->6->7
Output:
4 2 1 3 6 5 7
Explanation :
The BST formed using elements of the 
linked list is,
        4
      /   \
     2     6
   /  \   / \
  1   3  5   7  
Hence, preorder traversal of this 
tree is 4 2 1 3 6 5 7
Example 2:
Input:
Linked List : 1->2->3->4
Ouput:
3 2 1 4
Explanation:
The BST formed using elements of the 
linked list is,
      3   
    /  \  
   2    4 
 / 
1
Hence, the preorder traversal of this 
tree is 3 2 1 4
Your task :
You don't have to read input or print anything. Your task is to complete the function sortedListToBST(), which takes head of the linked list as an input parameter and returns the root of the BST created.
 
Expected Time Complexity: O(N), N = number of Nodes
Expected Auxiliary Space: O(N), N = number of Nodes
 
Constraints:
1 ≤ Number of Nodes ≤ 10^{6}
1 ≤ Value of each node ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3



'''

#LinkedList Node

class LNode:

    def __init__(self, data):   # data -> value stored in node

        self.data = data

        self.next = None

        

#Tree Node        

class TNode:

    def __init__(self, data):

        self.data=data

        self.left = self.right = None

'''



class Solution:

    def sortedListToBST(self, head):

        #code here

Solutions:
class Solution:

	def sortedListToBST(self, head):
		temp = head
		arr = []
		while temp:
			arr.append(temp.data)
			temp = temp.next

		def build(arr, start, end):
			if start > end:
				return None
			if (start + end) % 2 == 0:
				mid = (start + end) // 2
			else:
				mid = (start + end) // 2 + 1
			node = TNode(arr[mid])
			node.left = build(arr, start, mid - 1)
			node.right = build(arr, mid + 1, end)
			return node
		return build(arr, 0, len(arr) - 1)


class Solution:

	def sortedListToBST(self, head):
		temp = head
		li = []
		while temp:
			li.append(temp.data)
			temp = temp.next

		def helper(li, s, e):
			if s > e:
				return None
			if (s + e) % 2 == 0:
				mid = (s + e) // 2
			else:
				mid = (s + e) // 2 + 1
			root = TNode(li[mid])
			root.left = helper(li, s, mid - 1)
			root.right = helper(li, mid + 1, e)
			return root
		return helper(li, 0, len(li) - 1)


class Solution:

	def sortedListToBST(self, head):
		if head is None:
			return None
		(prev, slow, fast) = (None, head, head)
		while fast and fast.next:
			prev = slow
			slow = slow.next
			fast = fast.next.next
		if prev is not None:
			prev.next = None
		node = TNode(slow.data)
		node.left = self.sortedListToBST(head if prev else None)
		node.right = self.sortedListToBST(slow.next)
		return node


class Solution:

	def sortedListToBST(self, head):
		nums = []
		while head != None:
			nums.append(head.data)
			head = head.next

		def conBST(nums):
			if not nums:
				return None
			mid = len(nums) // 2
			root = TNode(nums[mid])
			root.left = conBST(nums[:mid])
			root.right = conBST(nums[mid + 1:])
			return root
		return conBST(nums)


class Solution:

	def count_nodes(self, head):
		cnt = 0
		temp = head
		while temp:
			temp = temp.next
			cnt += 1
		return cnt

	def get_mid(self, head):
		if head is None:
			return
		slow = head
		fast = head.next
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		cnt = self.count_nodes(head)
		if cnt % 2 == 0:
			return slow.next
		else:
			return slow

	def solve(self, head):
		if head is None:
			return None
		if head.next is None:
			root = TNode(head.data)
			return root
		mid_node = self.get_mid(head)
		if mid_node == head:
			root = TNode(mid_node.data)
			root.right = self.solve(mid_node.next)
			return root
		elif mid_node:
			temp = head
			while temp.next != mid_node:
				temp = temp.next
			temp.next = None
			root = TNode(mid_node.data)
			root.left = self.solve(head)
			root.right = self.solve(mid_node.next)
			return root

	def sortedListToBST(self, head):
		return self.solve(head)


class Solution:

	def sortedListToBST(self, head):
		a = []
		while head is not None:
			a.append(TNode(head.data))
			head = head.next
		return self.sortedArrayToBST(a)

	def sortedArrayToBST(self, nums):
		if len(nums) == 0:
			return
		mid = len(nums) // 2
		ans = nums[mid]
		ans.left = self.sortedArrayToBST(nums[0:mid])
		ans.right = self.sortedArrayToBST(nums[mid + 1:])
		return ans


class LNode:

	def __init__(self, data):
		self.data = data
		self.next = None

class TNode:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None

class Solution:

	def sortedListToBST(self, head):

		def build(a, mid, root):
			left = []
			right = []
			if root:
				root.data = a[mid]
				left = a[:mid]
				right = a[mid + 1:]
				if left:
					root.left = TNode(None)
					build(left, len(left) // 2, root.left)
				if right:
					root.right = TNode(None)
					build(right, len(right) // 2, root.right)
		a = []
		temp = head
		while temp:
			a.append(temp.data)
			temp = temp.next
		n = len(a)
		mid = n // 2
		root = TNode(a[mid])
		build(a, mid, root)
		return root


class Solution:

	def divide(self, head):
		l = 0
		temp = head
		while temp:
			l += 1
			temp = temp.next
		Llen = l // 2 - 1
		temp = head
		for i in range(Llen):
			temp = temp.next
		rest = temp.next
		temp.next = None
		mid = rest
		rest = rest.next
		mid.next = None
		return (head, mid, rest)

	def util(self, root, head):
		if head == None:
			return None
		if head.next == None:
			return TNode(head.data)
		(l, m, r) = self.divide(head)
		root = TNode(m.data)
		root.left = self.util(root, l)
		root.right = self.util(root, r)
		return root

	def sortedListToBST(self, head):
		root = self.util(None, head)
		return root


class Solution:

	def sortedListToBST(self, head):
		t = head
		a = []
		while t:
			a.append(t.data)
			t = t.next

		def build(a, s, e):
			if s > e:
				return None
			if (s + e) % 2 == 0:
				m = (s + e) // 2
			else:
				m = (s + e) // 2 + 1
			node = TNode(a[m])
			node.left = build(a, s, m - 1)
			node.right = build(a, m + 1, e)
			return node
		return build(a, 0, len(a) - 1)


class Solution:

	def sortedListToBST(self, head):

		def findmid(head, end):
			slow = head
			fast = head
			while fast != end and fast.next != end:
				fast = fast.next.next
				slow = slow.next
			return slow

		def rec(head, end):
			m = findmid(head, end)
			if head == end:
				return
			new = TNode(m.data)
			new.left = rec(head, m)
			new.right = rec(m.next, end)
			return new
		return rec(head, None)


class Solution:

	def sortedListToBST(self, head):

		def _convert_linked_to_list(head):
			to_return = []
			this_node = head
			while this_node.next:
				to_return.append(this_node.data)
				this_node = this_node.next
			to_return.append(this_node.data)
			return to_return

		def _build_BTS(list_segment):
			if not list_segment:
				return None
			center_i = int(len(list_segment) / 2)
			center_node = TNode(list_segment[center_i])
			center_node.left = _build_BTS(list_segment[:center_i])
			center_node.right = _build_BTS(list_segment[center_i + 1:])
			return center_node
		as_list = _convert_linked_to_list(head)
		return _build_BTS(as_list)


class Solution:

	def sortedListToBST(self, head):
		elems = []
		while head:
			elems.append(head.data)
			head = head.next
		return self._sortedListToBST(elems, 0, len(elems) - 1)

	def _sortedListToBST(self, elems, start, end):
		if end < start:
			return None
		m = (start + end + 1) // 2
		node = TNode(elems[m])
		node.left = self._sortedListToBST(elems, start, m - 1)
		node.right = self._sortedListToBST(elems, m + 1, end)
		return node


import math

class Solution:

	def sortedListToBST(self, head):
		ptr = head
		n = 0
		arr = []
		while ptr != None:
			arr.append(ptr.data)
			ptr = ptr.next
			n += 1

		def solve(l, h):
			if l > h:
				return None
			if l == h:
				return TNode(arr[l])
			m = math.ceil((l + h) / 2)
			node = TNode(arr[m])
			node.left = solve(l, m - 1)
			node.right = solve(m + 1, h)
			return node
		return solve(0, n - 1)


class Solution:

	def sortedListToBST(self, head):

		def fun(low, high, a):
			if (low + high) % 2 == 0:
				mid = (low + high) // 2
				return mid
			else:
				mid = (low + high) // 2
				return mid + 1
		a = []
		temp = head
		while temp:
			a.append(temp.data)
			temp = temp.next

		def make(low, high, a):
			if low > high:
				return None
			mid = fun(low, high, a)
			root = TNode(a[mid])
			root.left = make(low, mid - 1, a)
			root.right = make(mid + 1, high, a)
			return root
		return make(0, len(a) - 1, a)


class Solution:

	def sortedListToBST(self, head):
		if head is None:
			return None
		size = 0
		node = head
		while node is not None:
			size += 1
			node = node.next
		return self.helper(head, size)

	def helper(self, head, size):
		mid = size // 2
		i = 0
		lnode = head
		while i < mid:
			i += 1
			lnode = lnode.next
		tnode = TNode(lnode.data)
		if mid + 1 < size:
			tnode.right = self.helper(lnode.next, size - mid - 1)
		if 0 < mid:
			tnode.left = self.helper(head, mid)
		return tnode


class Solution:

	def sortedListToBST(self, head):
		lis = []
		while head != None:
			lis.append(head.data)
			head = head.next

		def fun(lis):
			if len(lis) == 1:
				return TNode(lis[0])
			mid = len(lis) // 2
			node = TNode(lis[mid])
			node.left = fun(lis[:mid])
			if mid + 1 < len(lis):
				node.right = fun(lis[mid + 1:])
			return node
		return fun(lis)


class Solution:

	def sortedListToBST(self, head):
		temp = head
		l1 = []
		while temp:
			l1.append(temp.data)
			temp = temp.next

		def construct(l, h):
			if l > h:
				return None
			mid = (l + h + 1) // 2
			nn = TNode(l1[mid])
			nn.left = construct(l, mid - 1)
			nn.right = construct(mid + 1, h)
			return nn
		return construct(0, len(l1) - 1)


import math

class Solution:

	def sortedListToBST(self, head):

		def build(res, s, e):
			if s > e:
				return None
			m = math.ceil(s + (e - s) / 2)
			root = TNode(res[m])
			root.left = build(res, s, m - 1)
			root.right = build(res, m + 1, e)
			return root
		temp = head
		res = []
		while temp:
			res.append(temp.data)
			temp = temp.next
		return build(res, 0, len(res) - 1)


class Solution:

	def create_bst(self, data_lst):
		if data_lst:
			mid = len(data_lst) // 2
			root = TNode(data_lst[mid])
			root.left = self.create_bst(data_lst[:mid])
			root.right = self.create_bst(data_lst[mid + 1:])
			return root

	def sortedListToBST(self, head):
		node_data = []
		while head:
			node_data.append(head.data)
			head = head.next
		tree = self.create_bst(node_data)
		return tree


class Solution:

	def findMiddle(self, head):
		if head == None or head.next == None:
			return head
		tur = head
		hare = head.next
		while hare.next and hare.next.next:
			tur = tur.next
			hare = hare.next.next
		return tur

	def buildBST(self, head):
		if head == None:
			return head
		if head.next == None:
			node = TNode(head.data)
			return node
		middle = self.findMiddle(head)
		nxt = middle.next
		middle.next = None
		root = TNode(nxt.data)
		root.left = self.buildBST(head)
		root.right = self.buildBST(nxt.next)
		return root

	def sortedListToBST(self, head):
		if head == None:
			return None
		if head.next == None:
			return TNode(head.data)
		if head.next.next == None:
			node = TNode(head.next.data)
			node.left = TNode(head.data)
			return node
		return self.buildBST(head)


class Solution:

	def __init__(self):
		self.head = None

	def Length(self, head):
		count = 0
		temp = head
		while temp != None:
			count += 1
			temp = temp.next
		return count

	def SortedListToBST(self, n):
		if n <= 0:
			return None
		l = self.SortedListToBST(n // 2)
		root = TNode(self.head.data)
		self.head = self.head.next
		root.left = l
		root.right = self.SortedListToBST(n - n // 2 - 1)
		return root

	def sortedListToBST(self, head):
		self.head = head
		n = self.Length(head)
		root = self.SortedListToBST(n)
		return root


class Solution:

	def printBST(self, arr):
		if len(arr) == 0:
			return None
		midd = len(arr) // 2
		root = TNode(arr[midd])
		root.left = self.printBST(arr[:midd])
		root.right = self.printBST(arr[midd + 1:])
		return root

	def sortedListToBST(self, head):
		arr = []
		temp = head
		while temp:
			arr.append(temp.data)
			temp = temp.next
		return self.printBST(arr)


import math

class Solution:

	def sortedListToBST(self, head):

		def converttoarray(head):
			arr = []
			while head:
				arr.append(head.data)
				head = head.next
			return arr

		def arrtoTree(left, right):
			if left > right:
				return None
			mid = math.ceil((left + right) / 2)
			root = TNode(arr[mid])
			root.left = arrtoTree(left, mid - 1)
			root.right = arrtoTree(mid + 1, right)
			return root
		arr = converttoarray(head)
		root = arrtoTree(0, len(arr) - 1)
		return root


class Solution:

	def sortedListToBST(self, head):
		l = []
		while head != None:
			l.append(head.data)
			head = head.next

		def fun(a):
			if len(a) == 0:
				return None
			head = TNode(a[len(a) // 2])
			head.left = fun(a[0:len(a) // 2])
			head.right = fun(a[len(a) // 2 + 1:])
			return head
		x = fun(l)
		return x


class Solution:

	def sortedListToBST(self, head):
		arr = []
		while head:
			arr.append(head.data)
			head = head.next
		root = self.totree(arr, 0, len(arr) - 1)
		return root

	def totree(self, arr, left, right):
		if left > right:
			return
		if (left + right) % 2 == 0:
			mid = (left + right) // 2
		else:
			mid = (left + right) // 2 + 1
		root = TNode(arr[mid])
		root.left = self.totree(arr, left, mid - 1)
		root.right = self.totree(arr, mid + 1, right)
		return root


class Solution:

	def solve(self, head, n):
		if n <= 0 or head[0] == None:
			return
		mid = n // 2
		left = self.solve(head, mid)
		root = TNode(head[0].data)
		root.left = left
		head[0] = head[0].next
		root.right = self.solve(head, n - mid - 1)
		return root

	def sortedListToBST(self, head):
		count = 0
		temp = head
		while temp:
			count += 1
			temp = temp.next
		head = [head]
		root = self.solve(head, count)
		return root


import math

class Solution:

	def inorder(self, root, head):
		temp = TNode(head.data)
		if head.next:
			head = head.next
		else:
			return
		if head.data < temp.data:
			temp.right = self.inorder(temp, head)
		else:
			temp.left = self.inorder(temp, head)

	def toarr(self, head):
		arr = []
		while head:
			arr.append(head.data)
			head = head.next
		return arr

	def arrToBST(self, arr, Min, Max):
		if Min > Max:
			return None
		mid = math.ceil((Min + Max) / 2)
		root = TNode(arr[mid])
		root.left = self.arrToBST(arr, Min, mid - 1)
		root.right = self.arrToBST(arr, mid + 1, Max)
		return root

	def sortedListToBST(self, head):
		arr = self.toarr(head)
		root = self.arrToBST(arr, 0, len(arr) - 1)
		return root


class Solution:

	def sortedListToBST(self, head):
		if not head:
			return None
		return self.bst(head, None)

	def bst(self, head, tail):
		if head == tail:
			return None
		fast = slow = head
		while fast != tail and fast.next != tail:
			fast = fast.next.next
			slow = slow.next
		node = TNode(slow.data)
		node.left = self.bst(head, slow)
		node.right = self.bst(slow.next, tail)
		return node


class Solution:

	def constructBST(self, leftHead, rightHead):
		if leftHead == rightHead:
			return None
		(slow, fast) = (leftHead, leftHead)
		while fast != rightHead and fast.next != rightHead:
			slow = slow.next
			fast = fast.next.next
		root = TNode(slow.data)
		root.left = self.constructBST(leftHead, slow)
		root.right = self.constructBST(slow.next, rightHead)
		return root

	def sortedListToBST(self, head):
		if not head:
			return None
		if not head.next:
			root = TNode(head.data)
			return root
		return self.constructBST(head, None)


import math

class Solution:

	def sortedListToBST(self, head):

		def transform(i, j):
			if i <= j:
				mid = math.ceil((i + j) / 2)
				new = TNode(A[mid])
				new.left = transform(i, mid - 1)
				new.right = transform(mid + 1, j)
				return new
		s = head
		A = []
		while s:
			A.append(s.data)
			s = s.next
		return transform(0, len(A) - 1)


class Solution:

	def sortedListToBST(self, head):
		return self.helper(head, None)

	def helper(self, start, end):
		if start == end:
			return None
		slow = start
		fast = start
		while fast != end and fast.next != end:
			slow = slow.next
			fast = fast.next.next
		root = TNode(slow.data)
		root.left = self.helper(start, slow)
		root.right = self.helper(slow.next, end)
		return root


class Solution:

	def __init__(self):
		self.head = None

	def count(self, head):
		l = 0
		while head:
			l += 1
			head = head.next
		return l

	def makebst(self, l):
		if l <= 0:
			return None
		left = self.makebst(l // 2)
		root = TNode(self.head.data)
		root.left = left
		self.head = self.head.next
		root.right = self.makebst(l - l // 2 - 1)
		return root

	def sortedListToBST(self, head):
		self.head = head
		return self.makebst(self.count(head))


class Solution:

	def sortedListToBST(self, head):
		if not head:
			return None
		if not head.next:
			return TNode(head.data)
		(slow, fast) = (head, head.next.next)
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		root = TNode(slow.next.data)
		right_head = slow.next.next
		slow.next = None
		root.right = self.sortedListToBST(right_head)
		root.left = self.sortedListToBST(head)
		return root


class Solution:

	def bst(self, li, s, e):
		if s > e:
			return None
		m = (s + e + 1) // 2
		temp = TNode(li[m])
		temp.left = self.bst(li, s, m - 1)
		temp.right = self.bst(li, m + 1, e)
		return temp

	def sortedListToBST(self, head):
		li = []
		count = 0
		while head:
			count += 1
			li.append(head.data)
			head = head.next
		s = 0
		e = count - 1
		return self.bst(li, s, e)


import math

class Solution:

	def sortedListToBST(self, head):
		nums = []
		h = head
		while h:
			nums.append(h.data)
			h = h.next
		root = self.d(nums, 0, len(nums) - 1)
		return root

	def d(self, nums, i, j):
		if i > j:
			return None
		if i >= 0 and j < len(nums):
			m = math.ceil((i + j) / 2)
			root = TNode(nums[m])
			root.left = self.d(nums, i, m - 1)
			root.right = self.d(nums, m + 1, j)
			return root
		return None


class Solution:

	def sortedListToBST(self, head):
		self.List = []
		node = head
		while node is not None:
			self.List.append(node.data)
			node = node.next
		treeHead = self.populateTree(0, len(self.List))
		return treeHead

	def populateTree(self, st, ed):
		if st == ed:
			return None
		mid = (st + ed) // 2
		node = TNode(self.List[mid])
		if ed - st == 1:
			return node
		node.left = self.populateTree(st, mid)
		node.right = self.populateTree(mid + 1, ed)
		return node


class Solution:

	def sortedListToBST(self, head):

		def center(node):
			slow = node
			fast = node.next.next
			while fast and fast.next:
				slow = slow.next
				fast = fast.next.next
			return slow

		def f(node):
			if not node:
				return None
			if not node.next:
				return TNode(node.data)
			if not node.next.next:
				left = TNode(node.data)
				t = TNode(node.next.data)
				t.left = left
				return t
			cnode = center(node)
			rnode = cnode.next
			cnode.next = None
			left = f(node)
			right = f(rnode.next)
			t = TNode(rnode.data)
			t.left = left
			t.right = right
			return t
		return f(head)


class Solution:

	def sortedListToBST(self, head):
		n = countNodes(head)
		return sortedListToBSTRecur([head], n)

def sortedListToBSTRecur(head_ref, n):
	if n <= 0:
		return None
	left = sortedListToBSTRecur(head_ref, n // 2)
	root = TNode(head_ref[0].data)
	root.left = left
	head_ref[0] = head_ref[0].next
	root.right = sortedListToBSTRecur(head_ref, n - n // 2 - 1)
	return root

def countNodes(head):
	count = 0
	current = head
	while current:
		count += 1
		current = current.next
	return count


class Solution:

	def arr2bst(self, arr):
		if not arr:
			return None
		head_i = len(arr) >> 1
		head = TNode(arr[head_i])
		head.left = self.arr2bst(arr[:head_i])
		head.right = self.arr2bst(arr[head_i + 1:])
		return head

	def sortedListToBST(self, head):
		arr = []
		while head != None:
			arr.append(head.data)
			head = head.next
		return self.arr2bst(arr)


import math

def createBST(arr, l, r):
	if l > r:
		return None
	m = math.ceil((l + r) / 2)
	ptr = TNode(arr[m])
	ptr.left = createBST(arr, l, m - 1)
	ptr.right = createBST(arr, m + 1, r)
	return ptr

class Solution:

	def sortedListToBST(self, head):
		arr = []
		while head:
			arr.append(head.data)
			head = head.next
		return createBST(arr, 0, len(arr) - 1)


class Solution:

	def sortedListToBST(self, head):
		if not head:
			return None
		if not head.next:
			return TNode(head.data)
		prev = LNode(-1)
		prev.next = slow = head
		fast = head
		while slow and fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			prev = prev.next
		root = TNode(slow.data)
		prev.next = None
		root.left = self.sortedListToBST(head)
		root.right = self.sortedListToBST(slow.next)
		return root


class Solution:

	def sortedListToBST(self, head):

		def fun(a, low, high):
			if (low + high) % 2 == 0:
				mid = (low + high) // 2
				return mid
			else:
				mid = (low + high) // 2
				return mid + 1

		def good(l, r):
			if l > r:
				return None
			m = fun(a, l, r)
			new = TNode(a[m])
			new.left = good(l, m - 1)
			new.right = good(m + 1, r)
			return new

		def findlength(head):
			curr = head
			cnt = 0
			while curr != None:
				cnt = cnt + 1
				curr = curr.next
			return cnt

		def convertArr(head):
			len1 = findlength(head)
			arr = []
			index = 0
			curr = head
			while curr != None:
				arr.append(curr.data)
				curr = curr.next
			return arr
		a = convertArr(head)
		return good(0, len(a) - 1)


class Solution:

	def sortedListToBST(self, head):
		if not head:
			return None
		_res = []
		while head:
			_res.append(head.data)
			head = head.next
		return self._bst(_res, 0, len(_res) - 1)

	def _bst(self, _res, low, high):
		if low > high:
			return None
		if (low + high) % 2 == 0:
			mid = (low + high) // 2
		else:
			mid = (low + high) // 2
			mid += 1
		root = TNode(_res[mid])
		root.left = self._bst(_res, low, mid - 1)
		root.right = self._bst(_res, mid + 1, high)
		return root


class Solution:

	def sortedListToBST(self, head):
		if not head:
			return
		if not head.next:
			l = TNode(head.data)
			return l
		(p, q) = (head, head)
		while q and q.next:
			r = p
			p = p.next
			q = q.next
			if q:
				q = q.next
		right = p
		right = right.next
		r.next = None
		t = TNode(p.data)
		t.left = self.sortedListToBST(head)
		t.right = self.sortedListToBST(right)
		return t


class Solution:

	def bst(self, arr, start, end):
		if start > end:
			return None
		mid = (start + end + 1) // 2
		root = TNode(arr[mid])
		root.left = self.bst(arr, start, mid - 1)
		root.right = self.bst(arr, mid + 1, end)
		return root

	def sortedListToBST(self, head):
		arr = []
		while head:
			arr.append(head.data)
			head = head.next
		return self.bst(arr, 0, len(arr) - 1)


class Solution:

	def sortedListToBST(self, head):
		arr = []
		length = 0
		temp = head
		while temp:
			arr.append(temp.data)
			length += 1
			temp = temp.next

		def midcal(low, high):
			if (low + high) % 2 == 0:
				return (low + high) // 2
			return (low + high) // 2 + 1

		def Tree(low, high, data):
			if low > high:
				return None
			mid = midcal(low, high)
			root = TNode(arr[mid])
			root.left = Tree(low, mid - 1, arr)
			root.right = Tree(mid + 1, high, arr)
			return root
		return Tree(0, length - 1, arr)


class Solution:

	def sortedListToBST(self, head):
		if not head:
			return
		node = head
		nums = []
		while node:
			nums.append(node.data)
			node = node.next

		def helper(l, r):
			if l > r:
				return None
			if (l + r) % 2 == 0:
				m = (l + r) // 2
			else:
				m = (l + r) // 2 + 1
			root = TNode(nums[m])
			root.left = helper(l, m - 1)
			root.right = helper(m + 1, r)
			return root
		return helper(0, len(nums) - 1)


class Solution:

	def sortedListToBST(self, head):
		arr = []
		ptr = head
		while ptr != None:
			arr.append(ptr.data)
			ptr = ptr.next
		return self.construct_BST(None, arr)

	def construct_BST(self, root, arr):
		n = len(arr)
		if n == 0:
			return None
		index = int(n / 2)
		root = TNode(arr[index])
		root.left = self.construct_BST(root.left, arr[:index])
		root.right = self.construct_BST(root.right, arr[index + 1:])
		return root


class Solution:

	def sortedListToBST(self, head):
		List = []
		cur = head
		while cur:
			List.append(cur.data)
			cur = cur.next
		mid = len(List) // 2

		def CreateTree(l, r):
			if l >= r:
				return
			mid = (l + r) // 2
			Tree = TNode(List[mid])
			Tree.left = CreateTree(l, mid)
			Tree.right = CreateTree(mid + 1, r)
			return Tree
		return CreateTree(0, len(List))


class Solution:

	def inorder(self, arr):
		if not arr:
			return None
		mid = len(arr) // 2
		root = TNode(arr[mid])
		root.left = self.inorder(arr[:mid])
		root.right = self.inorder(arr[mid + 1:])
		return root

	def sortedListToBST(self, head):
		arr = list()
		temp = head
		while temp:
			arr.append(temp.data)
			temp = temp.next
		return self.inorder(arr)


class Solution:

	def construct(self, a):
		if len(a) == 0:
			return None
		g = len(a) // 2
		o = TNode(a[g])
		o.left = self.construct(a[:g])
		o.right = self.construct(a[g + 1:])
		return o

	def sortedListToBST(self, head):
		t = head
		a = []
		while t:
			a.append(t.data)
			t = t.next
		return self.construct(a)


class Solution:

	def bst(self, li):
		if not li:
			return None
		cen = len(li) // 2
		head = TNode(li[cen])
		head.left = self.bst(li[:cen])
		head.right = self.bst(li[cen + 1:])
		return head

	def sortedListToBST(self, head):
		data = []
		while head != None:
			data.append(head.data)
			head = head.next
		return self.bst(data)


class Solution:

	def sortedListToBST(self, head):
		cur = head
		n = 0
		while cur:
			n += 1
			cur = cur.next
		return self.solver(head, n)

	def solver(self, head, n):
		if n == 0 or head == None:
			return None
		mid = n // 2
		i = 0
		temp = head
		while i != mid:
			temp = temp.next
			i += 1
		head1 = TNode(temp.data)
		head1.left = self.solver(head, n // 2)
		if n % 2 == 1:
			head1.right = self.solver(temp.next, n // 2)
		else:
			head1.right = self.solver(temp.next, n // 2 - 1)
		return head1


class Solution:

	def sortedListToBST(self, head):
		data = []
		temp = head
		while temp:
			data.append(temp.data)
			temp = temp.next

		def midvalueBST(low, high, data):
			mid = (low + high) // 2
			if (low + high) % 2 == 0:
				return mid
			else:
				return mid + 1

		def constBST(low, high, data):
			if low > high:
				return None
			mid = midvalueBST(low, high, data)
			root = TNode(data[mid])
			root.left = constBST(low, mid - 1, data)
			root.right = constBST(mid + 1, high, data)
			return root
		return constBST(0, len(data) - 1, data)


class Solution:

	def sortedListToBST(self, head):
		cnt = 0
		temp = head
		while temp:
			temp = temp.next
			cnt += 1
		self.head = head
		return self.func(cnt)

	def func(self, n):
		if n < 1:
			return
		left = self.func(int(n / 2))
		root = TNode(self.head.data)
		root.left = left
		self.head = self.head.next
		root.right = self.func(n - int(n / 2) - 1)
		return root


class Solution:

	def sortedListToBST(self, head):
		if head == None:
			return None
		if head.next == None:
			return TNode(head.data)
		slow = head
		fast = head.next
		pr = None
		while fast:
			pr = slow
			slow = slow.next
			fast = fast.next
			if fast:
				fast = fast.next
		p = slow
		p = p.next
		pr.next = None
		root = TNode(slow.data)
		root.right = self.sortedListToBST(p)
		root.left = self.sortedListToBST(head)
		return root


class Solution:

	def sortedListToBST(self, head):
		val_list = []
		while head:
			val_list.append(head.data)
			head = head.next

		def helper(arr):
			if not arr:
				return None
			else:
				m = len(arr) // 2
				node = TNode(arr[m])
				node.left = helper(arr[:m])
				node.right = helper(arr[m + 1:])
				return node
		root = helper(val_list)
		return root


class Solution:

	def getMidNode(self, head):
		prev = None
		mid = head
		q = head.next
		while q is not None:
			prev = mid
			mid = mid.next
			q = q.next
			if q is not None:
				q = q.next
		return (prev, mid)

	def sortedListToBST(self, head):
		if head is None:
			return None
		(prev, mid) = self.getMidNode(head)
		if prev is None:
			ll = None
		else:
			ll = head
			prev.next = None
		rl = mid.next
		mid.next = None
		root = TNode(mid.data)
		root.left = self.sortedListToBST(ll)
		root.right = self.sortedListToBST(rl)
		return root


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def count_nodes(self, head):
		if head is None:
			return 0
		count = 1
		curr = head
		while curr.next:
			curr = curr.next
			count += 1
		return count

	def sortedListToBST_util(self, head, n):
		if n == 0:
			return None
		left = self.sortedListToBST_util(head, n // 2)
		root = TNode(head[0].data)
		head[0] = head[0].next
		root.left = left
		root.right = self.sortedListToBST_util(head, n - n // 2 - 1)
		return root

	def sortedListToBST(self, head):
		n = self.count_nodes(head)
		return self.sortedListToBST_util([head], n)


class Solution:

	def sortedListToBST(self, head):

		def create(head):
			if head is None:
				return head
			if head.next is None:
				return TNode(head.data)
			pre = None
			slow = head
			forw = head
			while forw is not None and forw.next is not None:
				pre = slow
				slow = slow.next
				forw = forw.next.next
			pre.next = None
			newNode = TNode(slow.data)
			newNode.left = create(head)
			newNode.right = create(slow.next)
			return newNode
		return create(head)


class Solution:

	def __init__(self):
		self.h = None

	def sortedListToBST(self, head):
		n = 0
		p = head
		while p:
			n += 1
			p = p.next

		def f(l, h):
			if l > h:
				return None
			if (l + h) % 2 == 0:
				mid = (l + h) // 2
			else:
				mid = (l + h) // 2 + 1
			left = f(l, mid - 1)
			node = TNode(self.h.data)
			self.h = self.h.next
			node.left = left
			node.right = f(mid + 1, h)
			return node
		self.h = head
		return f(0, n - 1)


class Solution:

	def sortedListToBST(self, head):
		nodes = 0
		curr = head
		while curr:
			nodes += 1
			curr = curr.next

		def make_tree(curr, subset):
			if subset == 1:
				return (TNode(curr.data), curr)
			half = subset // 2
			(left_root, curr) = make_tree(curr, half)
			curr = curr.next
			root = TNode(curr.data)
			root.left = left_root
			other_half = subset - (half + 1)
			if other_half != 0:
				(root.right, curr) = make_tree(curr.next, other_half)
			return (root, curr)
		curr = head
		return make_tree(curr, nodes)[0]


class Solution:

	def sortedListToBST(self, head):

		def middle(low, high, res):
			if (low + high) % 2 == 0:
				mid = (low + high) // 2
				return mid
			else:
				mid = (low + high) // 2
				return mid + 1
		res = []
		c = head
		while c:
			res.append(c.data)
			c = c.next

		def make(low, high, res):
			if low > high:
				return None
			mid = middle(low, high, res)
			root = TNode(res[mid])
			root.left = make(low, mid - 1, res)
			root.right = make(mid + 1, high, res)
			return root
		return make(0, len(res) - 1, res)


class Solution:

	def getmid(self, root):
		if not root:
			return None
		prev = slow = fast = root
		while fast and fast.next:
			prev = slow
			slow = slow.next
			fast = fast.next.next
		if prev:
			prev.next = None
		return slow

	def sortedListToBST(self, head):
		if not head:
			return None
		mid = self.getmid(head)
		root = TNode(mid.data)
		if mid == head:
			return root
		root.left = self.sortedListToBST(head)
		root.right = self.sortedListToBST(mid.next)
		return root


class Node:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None

def solve(head):
	if head is None:
		return
	if head.next is None:
		return Node(head.data)
	curr = head
	fast = head
	slow = head
	while fast and fast.next:
		curr = slow
		fast = fast.next.next
		slow = slow.next
	root = Node(slow.data)
	temp = slow.next
	curr.next = None
	root.left = solve(head)
	root.right = solve(temp)
	return root

class Solution:

	def sortedListToBST(self, head):
		return solve(head)


class TNode:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None

class Solution:

	def getdata(self, head):
		result = []
		temp = head
		while temp:
			result.append(temp.data)
			temp = temp.next
		root = self.buildbst(result)
		return root

	def buildbst(self, result):
		if len(result) == 0:
			return None
		else:
			mid = len(result) // 2
			root = TNode(result[mid])
			root.left = self.buildbst(result[:mid])
			root.right = self.buildbst(result[mid + 1:])
		return root

	def sortedListToBST(self, head):
		return self.getdata(head)


class Solution:

	def sortedListToBST(self, head):
		self.lst = []
		while head:
			self.lst.append(head.data)
			head = head.next

		def dfs(lst):
			if lst == []:
				return
			if len(lst) == 1:
				return TNode(lst[0])
			mid = len(lst) // 2
			node = TNode(lst[mid])
			node.left = dfs(lst[:mid])
			node.right = dfs(lst[mid + 1:])
			return node
		return dfs(self.lst)


import math

class Solution:

	def sortedListToBST(self, head):
		temp = []
		while head:
			temp.append(head.data)
			head = head.next
		return self.helper(0, len(temp) - 1, temp)

	def helper(self, l, r, temp):
		if l > r:
			return None
		mid = math.ceil((l + r) / 2)
		root = TNode(temp[mid])
		root.left = self.helper(l, mid - 1, temp)
		root.right = self.helper(mid + 1, r, temp)
		return root