Given a singly linked list of N nodes.
The task is to find the middle of the linked list. For example, if the linked list is
1-> 2->3->4->5, then the middle node of the list is 3.
If there are two middle nodes(in case, when N is even), print the second middle element.
For example, if the linked list given is 1->2->3->4->5->6, then the middle node of the list is 4.
Example 1:
Input:
LinkedList: 1->2->3->4->5
Output: 3 
Explanation: 
Middle of linked list is 3.
Example 2: 
Input:
LinkedList: 2->4->6->7->5->1
Output: 7 
Explanation: 
Middle of linked list is 7.
Your Task:
The task is to complete the function getMiddle() which takes a head reference as the only argument and should return the data at the middle node of the linked list.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 5000

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

Starter code:
# your task is to complete this function



'''

class node:

    def __init__(data):

        self.data = data

        self.next = None

'''

class Solution:

    #  Should return data of middle node. If linked list is empty, then  -1

    def findMid(self, head):

        # Code here

        # return the value stored in the middle node



Solutions:
class Solution:

	def findMid(self, head):
		pre = head
		nxt = head.next
		while pre and nxt:
			pre = pre.next
			try:
				nxt = nxt.next.next
			except:
				return pre.data
		return pre.data


class Solution:

	def findMid(self, head):
		l = 0
		temp = head
		while head is not None:
			l += 1
			head = head.next
		for i in range(0, l // 2):
			temp = temp.next
		return temp.data


class Solution:

	def findMid(self, head):
		(s, f) = (head, head)
		while f and f.next:
			s = s.next
			f = f.next.next
		return s.data


class Solution:

	def findMid(self, head):
		values = []
		while head:
			values.append(head.data)
			head = head.next
		if len(values) == 0:
			return -1
		else:
			return values[len(values) // 2]


class Solution:

	def findMid(self, head):
		r = 0
		(x, v) = (head, head)
		if not x:
			return -1
		while x:
			r += 1
			x = x.next
		h = r // 2 + 1
		c = 1
		v = head
		while c != h:
			v = v.next
			c += 1
		return v.data


class Solution:

	def findMid(self, h):
		l = h
		n = 0
		t = []
		while l:
			n += 1
			t.append(l.data)
			l = l.next
		m = n // 2
		return t[m]


class Solution:

	def findMid(self, head):
		fast = head
		slow = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		if slow:
			return slow.data
		return -1


class Solution:

	def findMid(self, head):
		if head is None:
			return -1
		cur_node = head
		count = 1
		while cur_node.next is not None:
			cur_node = cur_node.next
			count += 1
		mid = count // 2
		cur_node = head
		for i in range(mid):
			cur_node = cur_node.next
		return cur_node.data


class Solution:

	def findMid(self, head):
		if head.next is None:
			return head.data
		elif head.next.next is None:
			return head.next.data
		i = 1
		temp = head
		while temp.next is not None:
			temp = temp.next
			i += 1
		m = i // 2 + 1
		temp = head
		j = 1
		while temp.next is not None:
			if m == j:
				return temp.data
				break
			temp = temp.next
			j += 1


class Solution:

	def findMid(self, head):
		if head == None:
			return -1
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		return slow.data
MOD = 10 ** 9 + 7


class Solution:

	def findMid(self, head):
		count = 0
		cur = head
		while cur is not None:
			cur = cur.next
			count += 1
		n = int(count / 2)
		cur = head
		for i in range(n):
			cur = cur.next
		return cur.data


class Solution:

	def findMid(self, head):
		c = []
		while head:
			c.append(head.data)
			head = head.next
		k = len(c)
		if k % 2 == 0:
			return c[k // 2]
		else:
			return c[k // 2]


class Solution:

	def findMid(self, head):
		a = []
		while head:
			a.append(head.data)
			head = head.next
		if len(a) % 2 == 0:
			return a[len(a) // 2]
		return a[len(a) // 2]


class Solution:

	def findMid(self, head):
		l = 0
		t = head
		while t is not None:
			l += 1
			t = t.next
		if l % 2 == 0:
			mid = l // 2
		else:
			mid = l // 2
		i = 0
		t = head
		while t is not None:
			if i == mid:
				return t.data
			t = t.next
			i += 1


class Solution:

	def findMid(self, head):
		temp = head
		count = 0
		while temp:
			count += 1
			temp = temp.next
		mid = count // 2
		temp1 = head
		while mid != 0:
			temp1 = temp1.next
			mid -= 1
		return temp1.data


class Solution:

	def findMid(self, head):
		(a, b) = (head, head)
		while b and b.next:
			a = a.next
			b = b.next.next
		return a.data


class Solution:

	def findMid(self, head):
		if head is None or head.next is None:
			return head.data
		slow = head
		fast = head.next
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
		count_ = 0
		while head:
			count_ += 1
			head = head.next
		return slow.data if count_ & 1 else slow.next.data


class Solution:

	def findMid(self, head):
		if head is None:
			return -1
		(s, f) = (head, head)
		while f and f.next:
			(s, f) = (s.next, f.next.next)
		return s.data


class Solution:

	def len(self, head):
		length = 1
		curr = head
		while curr.next != None:
			curr = curr.next
			length += 1
		return length

	def findMid(self, head):
		curr = head
		n = self.len(head)
		curr_idx = 1
		idx_req = (n + 1) // 2 + (n + 1) % 2
		if head == None:
			return -1
		while curr_idx != idx_req:
			curr = curr.next
			curr_idx += 1
		return curr.data


class Solution:

	def findMid(self, head):
		p = head
		n = 1
		while p.next != None:
			n = n + 1
			p = p.next
		m = n // 2 + 1
		n = 1
		while n != m:
			head = head.next
			n += 1
		return head.data


class Solution:

	def findMid(self, head):
		temp = head
		count = 0
		while temp != None:
			count += 1
			temp = temp.next
		if count % 2 == 0:
			i = 1
			j = count // 2
			temp = head
			while i < j + 1:
				temp = temp.next
				i += 1
			return temp.data
		else:
			i = 1
			j = count // 2
			temp = head
			while i <= j:
				temp = temp.next
				i += 1
			return temp.data


class Solution:

	def findMid(self, head):
		temp = head
		size = 0
		while temp != None:
			size += 1
			temp = temp.next
		reach = size // 2
		i = 0
		temp = head
		prev = None
		while temp != None and i <= reach:
			i += 1
			prev = temp
			temp = temp.next
		return prev.data


class Solution:

	def findMid(self, head):
		list1 = 0
		if head is None:
			return None
		slow = head
		fast = head
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
		return slow.data


class Solution:

	def findMid(self, head):
		a = list()
		while head:
			a.append(head.data)
			head = head.next
		n = len(a)
		return a[n // 2]


class Solution:

	def findMid(self, head):
		if head == None:
			return -1
		count = 0
		itr = head
		while itr:
			count += 1
			itr = itr.next
		itr = head
		if count % 2 != 0:
			middle = int(count // 2)
			for i in range(0, middle):
				itr = itr.next
			return itr.data
		else:
			middle2 = int(count // 2) + 1
			for i in range(0, middle2 - 1):
				itr = itr.next
			return itr.data


class Solution:

	def findMid(self, head):
		(current, prev) = (head, head)
		if head == None:
			return -1
		else:
			while current is not None and current.next is not None:
				prev = prev.next
				current = current.next.next
		return prev.data


class Solution:

	def getLength(self, head):
		temp = head
		l = 0
		while temp is not None:
			temp = temp.next
			l += 1
		return l

	def findMid(self, head):
		temp = head
		size = self.getLength(head)
		if size % 2 == 0:
			mid = size // 2
		else:
			mid = size // 2
		for i in range(mid):
			temp = temp.next
		return temp.data


class Solution:

	def findMid(self, head):
		if head is None or head.next is None:
			return head.data
		slow = head
		fast = head.next
		while fast is not None:
			slow = slow.next
			fast = fast.next
			if fast is None:
				break
			fast = fast.next
		return slow.data


class Solution:

	def findMid(self, head):
		if not head:
			return -1
		slow_ptr = head
		fast_ptr = head
		while fast_ptr and fast_ptr.next:
			slow_ptr = slow_ptr.next
			fast_ptr = fast_ptr.next.next
		return slow_ptr.data


import math

class Solution:

	def findMid(self, head):
		if not head:
			return 0
		total = 0
		p = head
		while p:
			total += 1
			p = p.next
		if total % 2 == 0:
			mid = total / 2 + 1
		else:
			mid = math.ceil(total / 2)
		p = head
		while p:
			if mid == 1:
				return p.data
			mid -= 1
			p = p.next


class Solution:

	def findMid(self, head):
		slow = head
		fast = head
		while fast is not None and fast.next is not None:
			slow = slow.next
			fast = fast.next.next
		return slow.data


class Solution:

	def findMid(self, head):
		one = head
		two = head
		while two and two.next:
			one = one.next
			two = two.next.next
		return one.data


class Solution:

	def findMid(self, head):
		s = head
		f = head
		while f is not None and f.next is not None:
			f = f.next.next
			s = s.next
		return s.data


class Solution:

	def findMid(self, head):
		if head.next:
			slow = head
			fast = head.next
		else:
			return head.data
		while fast:
			if fast.next:
				fast = fast.next.next
				slow = slow.next
			else:
				fast = fast.next
				slow = slow.next
		return slow.data


class Solution:

	def findMid(self, head):
		left = head
		right = head
		while right and right.next:
			left = left.next
			right = right.next.next
		return left.data


class Solution:

	def findMid(self, head):
		if head is None:
			return -1
		elif head.next is None:
			return head.data
		else:
			count = 1
			temp = head
			while temp.next:
				temp = temp.next
				count += 1
			mid = count // 2
			temp = head
			for i in range(1, mid):
				temp = temp.next
			return temp.next.data


class Solution:

	def findMid(self, head):
		res = []
		while head is not None:
			res.append(head.data)
			head = head.next
		return res[len(res) // 2]


class Solution:

	def findMid(self, head):
		pointer1 = head
		pointer2 = head
		while pointer2.next:
			pointer2 = pointer2.next
			if pointer2.next:
				pointer2 = pointer2.next
			pointer1 = pointer1.next
		return pointer1.data


class Solution:

	def findMid(self, head):
		length = 0
		temp = head
		while temp:
			length += 1
			temp = temp.next
		mid = length // 2
		temp = head
		c = 0
		while temp:
			if c == mid:
				return temp.data
				break
			c += 1
			temp = temp.next


import math

class Solution:

	def findMid(self, head):
		if head == None:
			return -1
		count = 0
		nextHead = head
		while nextHead != None:
			nextHead = nextHead.next
			count += 1
		if count % 2 != 0:
			sayi = math.floor(count / 2)
		else:
			sayi = count / 2
		countSayi = 0
		nextSayi = head
		while countSayi <= sayi - 1:
			nextSayi = nextSayi.next
			countSayi += 1
		return nextSayi.data


import math

class Solution:

	def findMid(self, head):
		item = head
		if item == None:
			return -1
		n = 0
		while item != None:
			n += 1
			item = item.next
		orta = 0
		item = head
		if n % 2 == 0:
			while orta < n / 2:
				orta += 1
				item = item.next
			return item.data
		else:
			while orta <= math.floor(n / 2) - 1:
				orta += 1
				item = item.next
			return item.data


import sys
sys.setrecursionlimit(5001)

class Solution:

	def findMid(self, head):
		global count
		global ans

		def f(curr):
			global count
			global ans
			if curr == None:
				return count - 1
			count += 1
			s = f(curr.next)
			if s == count // 2:
				ans = curr.data
			return s - 1
		count = 0
		ans = 0
		f(head)
		return ans


class Solution:

	def findMid(self, head):
		temp = head
		len = 0
		while temp != None:
			len += 1
			temp = temp.next
		len = len // 2
		while len != 0:
			head = head.next
			len -= 1
		return head.data


class Solution:

	def findMid(self, head):
		count = 0
		temp = head
		while temp:
			count += 1
			temp = temp.next
		n = count // 2
		for x in range(n):
			head = head.next
		return head.data


class Solution:

	def findMid(self, head):
		count = 0
		dummy = head
		while dummy:
			dummy = dummy.next
			count += 1
		if count % 2:
			x = count // 2
		else:
			x = count // 2
		mark = 0
		while head:
			if mark == x:
				return head.data
			mark += 1
			head = head.next


class Solution:

	def findMid(self, head):
		if head is None:
			return None
		ptr1 = head
		ptr2 = head
		while ptr2 is not None and ptr2.next is not None:
			ptr1 = ptr1.next
			ptr2 = ptr2.next.next
		return ptr1.data


class Solution:

	def findMid(self, head):
		temp = head
		c = 0
		while temp != None:
			c += 1
			temp = temp.next
		m = c // 2
		temp = head
		for i in range(m):
			temp = temp.next
		return temp.data


class Solution:

	def findMid(self, head):
		(tor, rab) = (head, head)
		while rab.next != None:
			if rab.next != None:
				rab = rab.next
				tor = tor.next
				if rab.next != None:
					rab = rab.next
		return tor.data


class Solution:

	def findMid(self, head):
		p = head
		q = head
		while q and q.next:
			p = p.next
			q = q.next.next
		return p.data


class Solution:

	def findMid(self, head):
		temp = head
		n = 0
		while temp:
			n += 1
			temp = temp.next
		n = n // 2
		temp = head
		while n:
			temp = temp.next
			n -= 1
		return temp.data


class Solution:

	def findMid(self, head):
		if head.next == None:
			return head.data
		temp = head
		temp2 = head
		len1 = 0
		while temp.next != None:
			temp = temp.next
			len1 += 1
		if len1 % 2 == 0:
			mid = int(len1 / 2)
		else:
			mid = int(len1 / 2) + 1
		while mid > 0:
			temp2 = temp2.next
			mid -= 1
		return temp2.data


class Solution:

	def findMid(self, head):
		sl_ptr = head
		fst_ptr = head
		while fst_ptr is not None and fst_ptr.next is not None:
			sl_ptr = sl_ptr.next
			fst_ptr = fst_ptr.next.next
		return sl_ptr.data


class Solution:

	def findMid(self, head):
		cur = head
		fast = head
		while fast and fast.next:
			cur = cur.next
			fast = fast.next.next
		return cur.data


class Solution:

	def findMid(self, head):
		fa = head
		sl = head
		while fa and fa.next:
			fa = fa.next.next
			sl = sl.next
		return sl.data


class Solution:

	def findMid(self, head):
		p = head
		q = head
		cnt = 0
		while p:
			p = p.next
			cnt += 1
		for i in range(cnt // 2):
			q = q.next
		return q.data


class Solution:

	def findMid(self, head):
		if not head:
			return -1
		ct = 0
		node = head
		while node:
			ct += 1
			node = node.next
		node = head
		for i in range(ct // 2):
			node = node.next
		return node.data