Find the Middle Element of the Linked List


#Problem statement

You are given the head of a Singly Linked List, the task is to find the middle of the linked list. If the number of nodes is even, then there would be two middle nodes, so return the second middle node.

#Example 1

#Input

head:  1->2->3->4->5 

#Output

3

#Explanation

There are 5 elements i.e. the count of elements is odd and the middle element is 3 therefore the middle element is 3.

image from tutorend.com

#Example 2

#Input

head:  1->2->3->4->5->6 

#Output

4

#Explanation

Here, there are even number of nodes in the linked list, So there would be two middle nodes 3 and 4, we will return the second middle node i.e. 4 as shown below.

image from tutorend.com

#Constraints

The number of Nodes in the Linked List is n >0 & n<= 100


#Solution 1: Brute force