Middle Node of a Linked List Problem Statement

Given the head node of a singly linked list, return a pointer to the middle node of the linked list. If the number of elements is odd, return the middle element. If the number of elements is even, return the latter of the two middle elements.

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, ending with -1 to signify the end of the linked list.

Output:

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

Example:

Input:

1<br>1 2 3 4 -1<br>

Output:

Pointer to the node with value 3

Explanation:

For the linked list 1->2->3->4->null, 3 is returned because it is the farther middle node from the head.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 4*10⁴
• -10⁹ <= data <= 10⁹
• data ≠ -1

Note:

1. You do not need to print anything; just implement the function.
2. For a linked list with a single node, the head node is the midpoint.
3. If no midpoint exists, return a null pointer.