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.
Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output: Node containing value 3.
Input: 1 -> 2 -> 3 -> 4 -> NULL
Output: Node containing value 3.
Input Parameters: The function has one argument, head node of the linked list.
Output: Return the middle node of the given list.
● 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.
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.
O(n).
O(1).
O(n) because that’s the size of input.
