This is a famous coding interview question that every programmer suppose to know. Here I am going to look at two different answers. First one is the obvious one, of course not the answer that the interviewer is looking for. Second one is the smart answer.
Method 1 - Using two traversals
First time traverse the linked list from head to tail and count the number of nodes. Next time traverse till number of nodes / 2 and find the middle node.
Method 2 - Using one traversal
This is the smart way of finding the middle of the linked list using two pointers. First pointer moves two nodes at a time while the second pointer moves one node at a time. When the fast pointer (which moves two nodes at a time) reach the tail the slow pointer (which moves one node at a time) will reach the middle node.
If this question was asked in an interview and if you answer with the method 1 interviewer will definitely ask if it is possible to find the middle element using one traversal. Then you can answer with the method 2. Obviously if it's an online coding interview better to go with method 2 as most companies will look for that answer.
I believe method 2 will be going to unlock new doors to your thinking pattern which will help to solve more complex algorithmic problems such as detecting a loop in a linked list.
Also, for interviewers this question is a smart question to start an algorithmic interview as it will lead to other complex problems which I will discuss in future articles.
