How to find middle element of Linked List in one pass?

This is frequently asked question for Java developers, How to find middle element of LinkedList in one pass if size is not given. In order to answer this question we need to understand how Linked List works. In case of singly linked list, each node contains data and next pointer. data holds the value and next pointer points to the next node, which holds address of the next node. And last element points to the null.

To find middle element of the linked list, first we need to find length of the linked list, for which we have to iterate through the list till end to find the length. If you think carefully this can be solved easily by 2 pointers, where first pointer points increments by 1 and second pointer increments by 2. So, when second pointer reaches the end of the linked list, first pointer will at the middle of the linked list.

 

Java program to find middle element of the Linked List

Output:

 

Further Reading

 

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
newest oldest most voted
Notify of
Ratnesh Mewani
Guest
Ratnesh Mewani

Thanks you have explained it very clearly. Can you also write a post on how to find nth element ?