Middle of Linked List

Given the head node of a singly linked list, your task is to return a pointer to the middle node of the linked list.

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

Example:

For Example:

Linked list: 1->2->3->4->null

Since there are 4 elements, we have two middle elements: 2 and 3. Return 3 as it is further from the head (1).

Input:

The first line 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, ending with -1 to signify the end.

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
• 1 <= N <= 4*10⁴
• -10⁹ <= data <= 10⁹
• data ≠ -1

Note:

1. You do not need to print anything, implementation of the function is required.
2. For a list of size 1, the head node itself is the midpoint.
3. If no midpoint exists, return a null pointer.