# """
# 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
# """

# 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
#         slow_ptr = head
# 		fast_ptr = head

# 		if head is not None:
# 			while (fast_ptr is not None and fast_ptr.next is not None):
# 				slow_ptr = slow_ptr.next
# 				fast_ptr = fast_ptr.next.next
# 			return slow_ptr.data
        


# #{ 
# #  Driver Code Starts
# # Initial Template for Python3

# # Node Class    
# class node:
#     def __init__(self):
#         self.data = None
#         self.next = None

# # Linked List Class
# class Linked_List:
#     def __init__(self):
#         self.head = None
#         self.tail = None
        
#     def insert(self, data):
#         if self.head == None:
#             self.head = node()
#             self.tail = self.head
#             self.head.data = data
#         else:
#             new_node = node()
#             new_node.data = data
#             new_node.next = None
#             self.tail.next = new_node
#             self.tail = self.tail.next

# def printlist(head):
#     temp = head
#     while temp is not None:
#         print(temp.data, end=" ")
#         temp = temp.next
#     print('')

# # Driver Program
# if __name__ == '__main__':
#     t = int(input())
#     for i in range(t):
#         list1 = Linked_List()
#         n = int(input())
#         values = list(map(int, input().strip().split()))
#         for i in values:
#             list1.insert(i)
#         ob = Solution()
#         print(ob.findMid(list1.head))


# # } Driver Code Ends

