Given the reference (pointer) to the head node of a linked list, the task is to find the middle node of it.
If there are two middle nodes(in case, when "n" is even), print the second middle element.
Input: 1->2->3->4->5->6->null
Output: 4
Input: 1->2->3->4->5->null
Output: 3
Solutions
Method 1: Using two pointers
Traverse linked list using two-pointers - "slow" and "fast".
Move the "slow" pointer by one node and the other "fast" pointer by two nodes.
When the fast pointer reaches the end, the slow pointer will reach the middle of the linked list.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).