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.

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.

Constraints

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

Solution 1: Brute force