Find Middle of Linked List

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

When the number of elements is odd, return the middle element. In the case of an even number of elements, return the one which is farther from the head node.

Example:

Consider the linked list: 1->2->3->4->null

Input:

head = [1, 2, 3, 4, -1]

Output:

Node with value 3

Explanation:

The linked list has 4 nodes, so there are 2 potential middle nodes (2 and 3). We select 3 because it's farther from the head node, which is 1.

Constraints:

• 1 <= T <= 50 where T is the number of test cases.
• 1 <= N <= 4*104 where N is the number of nodes in the linked list.
• -109 <= data <= 109 for each node value.
• Node values are not equal to -1.

Note:

1. You are not required to print anything; simply implement the function to return the pointer.

2. If the linked list has a single node, return the head node as the middle.

3. If there is no distinct middle (for empty lists), return a null pointer.