Middle of Linked List Problem Statement

Given the head node of a singly linked list, return a pointer pointing to the middle node of the linked list. In case the count of elements is even, return the node which is further from the head.

Example:

Input:

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

Output:

Pointer to node with value 3

Explanation:

The linked list has 4 elements, so we return the second of the two middle elements (i.e., node with value 3) as it is further from the head node.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 4*104
• -109 <= data <= 109
• The linked list nodes must not contain the value -1 (used only as a sentinel value for input parsing).
• Time Limit: 1 sec

Note:

• You do not need to print anything; just implement the function and return the answer.
• For a linked list with only one node, the head node itself is the middle.
• If no midpoint exists, return a null pointer.