Find Middle Element in a Linked List – Interview Question

Find Middle Element in a Linked List – Interview Question

October 12, 2018 Uncategorized 0


Find out middle element in a linked list.

Let’s see how to answer this question in a technical interview.

To begin with you can draw a linked list on the whiteboard. A linked list has nodes in it which are connected to each other. Each node has two components: the value and reference to next node. The head node points to the first element of the linked list.

So what’s the catch in the question?

You don’t know the number of elements in the linked list. You only have the reference to the head node.

Since you do not know the count, you will have to count them first. So you can iterate through the linked list, maintain a counter and find out the total count of nodes in the linked list.

Once you have the total count, you can divide it by 2 and restart from the beginning. Once you reach the middle element, you can return it.

In this solution, you had to make 2 passes through the linked list.

Next, the interviewer will want you to do this one iteration.

So what do you do?

 

The way you can find the middle element using one pass is by using 2 pointers to iterate through the list. One pointer moves at regular speed i.e. one element at a time and the other pointer moves fast i.e. 2 elements at a time. Once the fast pointer reaches the end of the linked list, the slow pointer will be at the middle position. So you can return the value at the slow pointer.

This way you have returned the middle element in one pass. The solution is certainly O(n) where n is the number of elements in the linked list.
To begin with, you might want to define how the node class will look like.

Class Node{
Int Value;
Node Next;
}

Next, we might want to define our slowPOinter and fastPointer. Here is the pseudo code for this problem.

If(Head == null)

  Return null

slowPointer = Head;

fastPointer = Head;

While(fastPointer!= null){

  fastPointer = fastPointer.Next;

  if(fastPointer!=null){

   slowPointer = slowPointer.Next;

   fastPointer = fastPointer.Next;

   }

 }

Return slowPointer.Value;

When you write the solution on the whiteboard please make sure to take care of all the edge cases.

The GitHub link to actual working code is here.

 

If you follow all these steps, then I would say that you have successfully answered the interview question.

I will be posing more such interview questions and how to answer them in my upcoming videos. Please make sure to subscribe to my channel Coach4Dev for more such problems. Until next time, Happy Coding!