Find middle element of a linked list in java

Last updated on March 25th, 2017 at 01:05 am

Previous
Next

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

This is one of the popular interview question.
In this post, we will discuss how to find middle element in linkedlist in most efficient way.

Java Linked List Interview Programs:

Assumption:

I am not using java LinkedList API here. If you use that API, you can directly find size of linkedlist using size() function and then locate length/2.

One of the algo for this would be:

  • Traverse the list and find the length of list
  • After finding length, again traverse the list and locate n/2 element from head of linkedlist.

Time complexity=time for finding length of list + time for locating middle element=o(n)+o(n) =o(n)
Space complexity= o(1).

Efficient approach:

Above approach will take two traversal but we can find middle element in one traversal also using following algo:

  1. Use two pointer fastptr and slowptr and initialize both to head of linkedlist
  2. Move fastptr by two nodes and slowptr by one node in each iteration.
  3. When fastptr reaches end of nodes, the slowptr pointer will be  pointing to middle element.

Lets create java program for it:

Logically linked list can be represented as:

Middle element is represented in red color.
Run above program, you will get following output:

Please go through java interview programs for more such programs.

Previous
Next

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.

Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog