Middle of a Linked List

You are given the head node of a singly linked list. Your task is to return a pointer pointing to the middle of the linked list.

If there is an odd number of elements, return the middle element. If there are an even number of elements, return the one that is farther from the head node.

Example:

Input:

1->2->3->4->null

Output:

3

Explanation:

The input linked list has 4 elements, with 2 and 3 as potential middles. We return 3 because it is farther from the head node 1.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases.
 The next ‘2*T’ lines represent the ‘T’ test cases.
 The first and only line of each test case contains integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list.

Output:

For each test case, return a pointer pointing to the node which is at the middle of the linked list. If no midpoint exists, return a null pointer.

Constraints:

• 1 <= T <= 50
• 0 <= N <= 4*10^4
• -10^9 <= data <= 10^9
• data ≠ -1

Note:

• You do not need to print anything, it has already been taken care of. Just implement the given function.
• For a linked list of size 1, the head node is the midpoint.
• If no midpoint exists, return a null pointer.