Find middle element of a linked list in java

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:

💻 Awesome Tech Resources:
  • Looking for ⚒️ tech jobs? Go to our job portal.
  • Looking for tech events? Go to tech events 🗓️ Calendar.️
  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.


import_contacts

You may also like:

Related Posts

  • 12 August

    Intersection of two linked lists

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post, we will see how to find Intersection of two linked lists. Problem Given two singly linked lists, find if two linked lists intersect. If they intersect, find intersection point. 💻 Awesome Tech Resources: Looking for […]

  • 12 October

    Implement Queue using Linked List in java

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post , we will see how to implement Queue using Linked List in java. Queue is abstract data type which demonstrates First in first out (FIFO) behaviour. We will implement same behaviour using Array. Although java provides implementation […]

  • 10 October

    Convert sorted Linked List to balanced BST

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post , we will see how to convert sorted LinkedList to balanced binary search tree. There are two ways to do it. Solution 1: It is very much similar to convert sorted array to BST. […]

  • 20 September

    Find length of Linked List in java

    If you want to practice data structure and algorithm programs, you can go through data structure and algorithm programs. In this post, we will see how to find length of Linked List in java. You can obviously use size() method of java Linked List class but here we are going to see how to find length […]

  • 20 September

    Implement singly linked list in java

    In this post, we will see how to implement singly linked list in java. It is one of the most used data structure. In singly linked list, Node has data and pointer to next node. It does not have pointer to the previous node. Last node ‘s next points to null, so you can iterate […]

  • 10 September

    Implement stack using Linked List in java

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this program, we will see how to implement stack using Linked List in java. The Stack is an abstract data type that demonstrates Last in first out (LIFO) behavior. We will implement the same behavior using […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.