Given an integer singly linked list L, find its middle element. L has n nodes.

If the list has even number of nodes, consider the second of the middle two nodes as the middle node.

##### Example One

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Output: Node containing value 3.

##### Example Two

Input: 1 -> 2 -> 3 -> 4 -> NULL

Output: Node containing value 3.

##### Notes

Input Parameters: The function has one argument, head node of the linked list.

Output: Return the middle node of the given list.

##### Constraints:

● 0 <= n <= 10^5

● -2 * 10^9 <= value contained in any node <= 2 * 10^9

● Do it in one pass over the linked list.

● If the given linked list is empty, return null.

#### Solution

A naive solution involves computing the length of the list and then traversing exactly half of that.

A faster approach is to use a slow pointer and a fast pointer, with the faster one traversing twice as fast.

By the time the fast one reaches the end of the list, the slower one is at the midpoint. This solution still takes O(n) time but it is faster than the naive one.

##### Time Complexity:

O(n).

##### Auxiliary Space Used:

O(1).

##### Space Complexity:

O(n) because that’s the size of input.