Given a linked list of size N and a key. The task is to insert the key in the middle of the linked list.
Example 1:
Input:
LinkedList = 1->2->4
key = 3
Output: 1 2 3 4
Explanation: The new element is inserted
after the current middle element in the
linked list.
Example 2:
Input:
LinkedList = 10->20->40->50
key = 30
Output: 10 20 30 40 50
Explanation: The new element is inserted
after the current middle element in the
linked list and Hence, the output is
10 20 30 40 50.
 
Your Task:
The task is to complete the function insertInMiddle() which takes head reference and element to be inserted as the arguments. The printing is done automatically by the driver code.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N <= 10^{4}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

'''

    Your task is to insert a new node in 

	the middle of the linked list with

	the given value.

	

	{

		# Node Class

		class Node:

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

		        self.data = data

		        self.next = None

	}

	

	Function Arguments: head (head of linked list), node 

	(node to be inserted in middle)

	Return Type: None, just insert the new node at mid.

'''

#Function to insert a node in the middle of the linked list.

def insertInMid(head,node):

    #code here

Solutions:
def insertInMid(head, node):
	p = head
	n = 1
	while p.next != None:
		p = p.next
		n += 1
	m = (n + 1) // 2
	n = 1
	p = head
	while p.next != None and n != m:
		p = p.next
		n += 1
	node.next = p.next
	p.next = node
	return head


def insertInMid(head, node):
	temp = head
	size = 0
	while temp != None:
		size += 1
		temp = temp.next
	if size % 2 == 0:
		i = 1
		j = size // 2
		temp = head
		prev = None
		while i < j + 1:
			prev = temp
			temp = temp.next
			i += 1
		node.next = prev.next
		prev.next = node
	else:
		i = 1
		j = size // 2
		temp = head
		while i <= j:
			temp = temp.next
			i += 1
		node.next = temp.next
		temp.next = node


def insertInMid(head, node):
	slow = head
	fast = head.next
	curr = head
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
	node.next = slow.next
	slow.next = node
	return head


def insertInMid(head, node):
	itr = 0
	temp = head
	while temp != None:
		itr = itr + 1
		temp = temp.next
	if itr % 2 == 0:
		itr = int(itr / 2)
	else:
		itr = int(itr / 2) + 1
	temp = head
	for i in range(itr - 1):
		temp = temp.next
	re = temp.next
	temp.next = node
	temp.next.next = re
	return temp


def insertInMid(head, node):
	counter = 0
	temp = head
	while temp:
		temp = temp.next
		counter += 1
	if counter % 2 == 0:
		mid = counter / 2
	elif counter % 2 == 1:
		mid = (counter + 1) / 2
	temp = head
	k = 0
	while mid > 1:
		mid -= 1
		temp = temp.next
	node.next = temp.next
	temp.next = node


def insertInMid(head, node):
	if head == None:
		return temp
	pos = 0
	cur = head
	while cur != None:
		pos += 1
		cur = cur.next
	cur = head
	if pos % 2 == 0:
		m = pos // 2
	else:
		m = (pos + 1) // 2
	for i in range(m - 1):
		cur = cur.next
	node.next = cur.next
	cur.next = node
	return head


def insertInMid(head, node):
	slow = head
	fast = head.next
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	temp = node
	temp.next = slow.next
	slow.next = temp


def insertInMid(head, node):
	temp = head
	length = 0
	while temp:
		length = length + 1
		temp = temp.next
	if length % 2 == 1:
		pos = length // 2 + 1
	else:
		pos = length // 2
	i = 0
	while i < pos:
		if i == 0:
			temp = head
		else:
			temp = temp.next
		i = i + 1
	node.next = temp.next
	temp.next = node


def insertInMid(head, node):
	if head is None:
		return
	if head.next is None:
		head.next = node
		return
	slow = head
	fast = head
	while fast != None and fast.next != None:
		fast = fast.next.next
		if fast == None:
			node.next = slow.next
			slow.next = node
		slow = slow.next
	temp = slow.next
	slow.next = node
	node.next = temp


def insertInMid(head, node):
	d = head
	n = head
	while n.next and n.next.next:
		d = d.next
		n = n.next.next
	node.next = d.next
	d.next = node
	return head


def insertInMid(head, node):
	temp = head
	l_len = 0
	if temp is None:
		return
	while temp is not None:
		l_len += 1
		temp = temp.next
	if l_len % 2 == 0:
		middle_ind = l_len // 2
	else:
		middle_ind = (l_len + 1) // 2
	temp = head
	for i in range(1, middle_ind):
		temp = temp.next
	node.next = temp.next
	temp.next = node


def insertInMid(head, node):
	slow = head
	fast = head.next
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	node.next = slow.next
	slow.next = node
	return head


def insertInMid(head, node):
	curr = head
	length = 0
	while curr:
		length += 1
		curr = curr.next
	if length % 2 == 0:
		count = length // 2
	else:
		count = (length + 1) // 2
	ptr = head
	while count > 1:
		ptr = ptr.next
		count -= 1
	node.next = ptr.next
	ptr.next = node
	return head


def insertInMid(head, node):
	if head == None:
		return node
	cur = head
	length = 0
	while cur != None:
		cur = cur.next
		length = length + 1
	if length % 2 is 0:
		mid = length // 2
	else:
		mid = (length + 1) // 2
	count = 1
	cur = head
	while count != mid:
		cur = cur.next
		count += 1
	node.next = cur.next
	cur.next = node
	return head


def insertInMid(head, node):
	x = node.data
	if head == None:
		head = Node(x)
	else:
		newNode = Node(x)
		slow = head
		fast = head.next
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		newNode.next = slow.next
		slow.next = newNode


def insertInMid(head, node):
	p = head
	q = head
	while q.next and q.next.next:
		p = p.next
		q = q.next.next
	node.next = p.next
	p.next = node
	return head


def insertInMid(head, node):
	current = head
	N = 0
	while current:
		N += 1
		current = current.next
	middle = int(N / 2 + 1) if N % 2 else N // 2
	current = head
	previous = None
	while middle:
		previous = current
		current = current.next
		middle -= 1
	node.next = current
	previous.next = node


def insertInMid(head, node):
	slow = head
	fast = head.next
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	s = Node(node)
	s.data.next = slow.next
	slow.next = s.data


def insertInMid(head, node):
	cou = 0
	curr = head
	mid = 0
	while curr:
		curr = curr.next
		cou += 1
	if cou % 2 == 0:
		mid = cou // 2
	elif cou % 2 == 1:
		mid = (cou + 1) // 2
	temp = head
	while mid > 1:
		mid -= 1
		temp = temp.next
	node.next = temp.next
	temp.next = node


def insertInMid(head, node):
	newnode = Node(node.data)
	if head is None:
		return newnode
	else:
		slow = head
		fast = head
		while fast != None and fast.next != None and (fast.next.next != None):
			slow = slow.next
			fast = fast.next.next
		newnode.next = slow.next
		slow.next = newnode
		return newnode


def insertInMid(head, node):
	temp = head
	n = 0
	while temp != None:
		n += 1
		temp = temp.next
	mid = round(n / 2, 1)
	i = 0
	temp = head
	while i < mid - 1:
		temp = temp.next
		i += 1
	node.next = temp.next
	temp.next = node


def insertInMid(head, node):
	if head is None:
		return node
	curr = head
	ln = 0
	count = 1
	while curr is not None:
		curr = curr.next
		ln += 1
	if ln % 2 is 0:
		middle = ln / 2
	else:
		middle = (ln + 1) / 2
	curr = head
	while count != middle:
		curr = curr.next
		count += 1
	node.next = curr.next
	curr.next = node
	return head


def insertInMid(head, node):
	slow = head
	fast = head.next
	while fast is not None and fast.next is not None:
		slow = slow.next
		fast = fast.next.next
	node.next = slow.next
	slow.next = node
	return True


def insertInMid(head, node):
	n = head
	count = 0
	while n != None:
		n = n.next
		count += 1
	n = head
	x = 1
	while x < count / 2:
		n = n.next
		x += 1
	node.next = n.next
	n.next = node


def insertInMid(head, node):
	if head == None:
		return node
	count = 0
	cur = head
	while cur:
		cur = cur.next
		count += 1
	if count % 2 == 0:
		c = count // 2
	else:
		c = count // 2 + 1
	res = 1
	cur = head
	while res < c and cur != None:
		cur = cur.next
		res += 1
	if cur != None:
		node.next = cur.next
		cur.next = node
		return head


def insertInMid(head, node):
	slow = head
	fast = head
	l = 1
	while fast != None and fast.next != None:
		if fast.next.next != None:
			l += 2
		elif fast.next != None:
			l += 1
		else:
			break
		temp = slow
		slow = slow.next
		fast = fast.next.next
	if l % 2 == 0:
		slow = temp
	node.next = slow.next
	slow.next = node
	return head


def insertInMid(head, node):
	curr = head
	l = 1
	while curr.next != None:
		l += 1
		curr = curr.next
	i = 0
	if l % 2 == 0:
		mid = l // 2 - 1
	else:
		mid = l // 2
	curr = head
	while i != mid:
		curr = curr.next
		i += 1
	node.next = curr.next
	curr.next = node


class Node:

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

def insertInMid(head, node):
	if not head:
		return node
	if not head.next:
		head.next = node
		return head
	slow = head
	fast = head.next.next if head.next else None
	while fast:
		slow = slow.next
		fast = fast.next.next if fast.next else None
	temp = slow.next
	slow.next = node
	node.next = temp
	return head


def insertInMid(head, node):
	temp = node
	if head == None:
		return temp
	curr = head
	n = 0
	while curr != None:
		n += 1
		curr = curr.next
	curr = head
	if n % 2 != 0:
		for i in range(n // 2):
			curr = curr.next
	else:
		for i in range(n // 2 - 1):
			curr = curr.next
	temp.next = curr.next
	curr.next = temp
	return head


def insertInMid(head, node):
	(slow, fast) = (head, head.next)
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next if fast.next else fast.next
	nxt = slow.next
	slow.next = node
	node.next = nxt
	return head


def insertInMid(head, node):
	slow = head
	fast = head.next
	while fast and fast.next is not None:
		slow = slow.next
		fast = fast.next.next
	slowNext = slow.next
	slow.next = node


def insertInMid(head, node):
	cur = head
	count = 0
	while cur:
		count += 1
		cur = cur.next
	mid = 0
	if count % 2 == 0:
		mid = count // 2
	else:
		mid = (count + 1) // 2
	cur = head
	while mid > 1:
		mid -= 1
		cur = cur.next
	curNext = cur.next
	cur.next = node


def insertInMid(head, node):
	temp = head
	count = 0
	n = 0
	while temp is not None:
		n += 1
		temp = temp.next
	count = n // 2
	temp = head
	if n % 2 == 0:
		count -= 1
		while count:
			count -= 1
			temp = temp.next
		new_node = node
		new_node.next = temp.next
		temp.next = new_node
		return head
	else:
		while count:
			count -= 1
			temp = temp.next
		new_node = node
		new_node.next = temp.next
		temp.next = new_node


def insertInMid(head, node):
	s = head
	f = head
	while f.next != None and f.next.next != None:
		s = s.next
		f = f.next.next
	node.next = s.next
	s.next = node
	return head


def insertInMid(head, node):
	count = 0
	curr = head
	while curr:
		count += 1
		curr = curr.next
	if count % 2 == 0:
		mid = count // 2 - 1
	else:
		mid = count // 2
	curr = head
	while mid:
		mid -= 1
		curr = curr.next
	node.next = curr.next
	curr.next = node


def insertInMid(head, node):
	temp = head
	n = Node(node)
	c = 0
	while temp != None:
		c += 1
		temp = temp.next
	if c % 2 == 0:
		mid = c // 2
	else:
		mid = c // 2 + 1
	temp = head
	k = 0
	while mid > 1:
		mid -= 1
		temp = temp.next
	node.next = temp.next
	temp.next = node


def insertInMid(head, node):
	curr = head
	count = 0
	while curr != None:
		count += 1
		curr = curr.next
	curr = head
	if count % 2 == 0:
		i = count / 2
	elif count % 2 == 1:
		i = (count + 1) / 2
	while i > 1:
		i -= 1
		curr = curr.next
	node.next = curr.next
	curr.next = node


def insertInMid(head, node):
	if head == None:
		return node
	curr = head
	l = 0
	while curr != None:
		curr = curr.next
		l += 1
	if l % 2 == 0:
		mid = l / 2
	else:
		mid = (l + 1) / 2
	count = 1
	curr = head
	while count != mid:
		curr = curr.next
		count += 1
	node.next = curr.next
	curr.next = node
	return head


def insertInMid(head, node):
	if head == None:
		return node
	curr = head
	length = 0
	while curr != None:
		curr = curr.next
		length = length + 1
	if length % 2 == 0:
		middle = length / 2
	else:
		middle = (length + 1) // 2
	count = 1
	curr = head
	while count != middle:
		curr = curr.next
		count += 1
	node.next = curr.next
	curr.next = node
	return head


def insertInMid(head, node):
	count = 0
	temp = head
	while temp:
		temp = temp.next
		count += 1
	if count % 2 == 0:
		mid = count / 2
	elif count % 2 == 1:
		mid = (count + 1) / 2
	temp = head
	while mid > 1:
		mid -= 1
		temp = temp.next
	node.next = temp.next
	temp.next = node


def insertInMid(head, node):
	slow = fast = head
	left_slow = head
	while fast and fast.next:
		left_slow = slow
		slow = slow.next
		fast = fast.next.next
	if fast == None:
		node.next = slow
		left_slow.next = node
	else:
		node.next = slow.next
		slow.next = node


def insertInMid(head, new_node):
	slow = head
	fast = head.next
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	new_node.next = slow.next
	slow.next = new_node


def insertInMid(head, node):
	if head is None:
		return node
	(prev, slow, fast) = (head, head, head)
	pos = 1
	while fast and fast.next:
		prev = slow
		slow = slow.next
		fast = fast.next.next
		pos += 1
	if fast:
		temp = slow.next
		node.next = temp
		slow.next = node
	else:
		temp = prev.next
		node.next = temp
		prev.next = node
	return head


def insertInMid(head, node):
	if head == None:
		return
	slow = fast = head
	while fast != None and fast.next != None:
		fast = fast.next.next
		if fast == None:
			break
		slow = slow.next
	node.next = slow.next
	slow.next = node
	return head


def insertInMid(head, node):
	i = 0
	a = head
	b = head
	while a:
		i = i + 1
		a = a.next
	if i % 2 == 0:
		poi = i // 2 - 1
	else:
		poi = i // 2
	while head and poi > 0:
		head = head.next
		poi -= 1
	node.next = head.next
	head.next = node
	return head


import math

def insertInMid(head, node):
	counter = 0
	if head == None:
		head = node
	node2 = head
	while node2:
		counter += 1
		node2 = node2.next
	pos = math.ceil(counter / 2)
	node3 = head
	counter1 = 0
	while node3:
		counter1 += 1
		if counter1 == pos:
			node.next = node3.next
			node3.next = node
		node3 = node3.next


def insertInMid(head, node):
	curr = head
	count = 0
	while curr.next != None:
		count += 1
		curr = curr.next
	c = head
	for i in range(count // 2):
		c = c.next
	node.next = c.next
	c.next = node
	return head


def insertInMid(head, node):
	if not head:
		return node
	slow = head
	fast = head
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	node.next = slow.next
	slow.next = node
	return head


def insertInMid(head, node):
	c = 0
	temp = head
	while temp:
		c += 1
		temp = temp.next
	if c % 2 == 0:
		c = c // 2
	else:
		c = (c + 1) // 2
	cur = head
	prev = None
	i = 0
	while i < c:
		prev = cur
		cur = cur.next
		i += 1
	prev.next = node
	node.next = cur
	return head


def insertInMid(head, node):
	temp = head
	temp1 = head
	length = 0
	while temp:
		temp = temp.next
		length = length + 1
	if length % 2 == 0:
		mid = length / 2
	elif length % 2 == 1:
		mid = (length + 1) / 2
	while mid > 1:
		mid = mid - 1
		temp1 = temp1.next
	node.next = temp1.next
	temp1.next = node


def insertInMid(head, node):
	fp = head
	sp = head
	while fp != None and fp.next != None and (fp.next.next != None):
		sp = sp.next
		fp = fp.next.next
	node.next = sp.next
	sp.next = node


def insertInMid(head, node):
	temp = node
	count = 0
	curr = head
	if head == None:
		return None
	while curr != None:
		curr = curr.next
		count += 1
	middle = count // 2
	if count % 2 == 0:
		middle -= 1
	else:
		middle = middle
	i = 0
	curr = head
	while i < middle:
		curr = curr.next
		i += 1
	temp.next = curr.next
	curr.next = temp
	return head


def insertInMid(head, node):
	new = node
	p = head
	i = 0
	while p:
		p = p.next
		i += 1
	if i % 2 == 0:
		mid = i / 2
	else:
		mid = (i + 1) / 2
	count = 1
	p = head
	while count != mid:
		p = p.next
		count += 1
	new.next = p.next
	p.next = new


def insertInMid(head, node):
	c = 0
	p = 0
	temp = head
	new_node = node
	while temp != None:
		c = c + 1
		temp = temp.next
	if c % 2 == 0:
		m = c // 2
	else:
		m = c // 2 + 1
	cu = pr = head
	while cu.next != None:
		p = p + 1
		if p == m:
			pr = cu
			break
		cu = cu.next
	new_node.next = pr.next
	pr.next = new_node


def insertInMid(head, node):
	if head == None:
		return None
	if head.next == None:
		head.next = node
		return None
	curr = head
	count = 0
	while curr:
		curr = curr.next
		count += 1
	curr = head
	prev = head
	if count % 2 != 0:
		while curr.next != None and curr != None:
			prev = prev.next
			curr = curr.next.next
		node.next = prev.next
		prev.next = node
	else:
		for i in range(count // 2):
			prev = curr
			curr = curr.next
		node.next = prev.next
		prev.next = node
	return None


def insertInMid(head, node):
	new = node
	temp = head
	mid = head
	prev = mid
	while temp is not None:
		temp = temp.next
		prev = mid
		mid = mid.next
		if temp is not None:
			temp = temp.next
	new.next = prev.next
	prev.next = new


def insertInMid(head, node):
	new = node
	temp = head
	c = 0
	while temp is not None:
		c += 1
		temp = temp.next
	temp = head
	mid = c // 2
	if c % 2 == 0:
		mid -= 1
	c = 0
	while c != mid:
		temp = temp.next
		c += 1
	new.next = temp.next
	temp.next = new


def insertInMid(head, node):
	count = 0
	temp = head
	while temp:
		count += 1
		temp = temp.next
	temp = head
	if count % 2 == 0:
		c = int(count / 2 - 1)
	else:
		c = int(count / 2)
	for i in range(c):
		temp = temp.next
	node.next = temp.next
	temp.next = node


def insertInMid(head, node):
	slow = head
	fast = head
	prev = None
	while fast and fast.next:
		prev = slow
		slow = slow.next
		fast = fast.next.next
	nextNode = slow.next
	if not fast:
		prev.next = node
		prev.next.next = slow
	else:
		slow.next = node
		slow.next.next = nextNode


def insertInMid(head, node):
	curr = head
	prev = None
	count = 0
	while curr:
		count += 1
		curr = curr.next
	lenOfLList = count
	count = 0
	curr = head
	if lenOfLList % 2 == 0:
		while count != lenOfLList // 2 - 1:
			count += 1
			curr = curr.next
		nextNode = curr.next
		curr.next = node
		curr.next.next = nextNode
	else:
		while count != lenOfLList // 2:
			count += 1
			curr = curr.next
		nextNode = curr.next
		curr.next = node
		curr.next.next = nextNode


def insertInMid(head, node):
	import math
	index = prevIndex = 0
	prevHead = head
	while head:
		if math.floor(index / 2) > prevIndex:
			prevIndex += 1
			prevHead = prevHead.next
		index += 1
		head = head.next
	temp = prevHead.next
	prevHead.next = node
	node.next = temp