Find middle element of linked list in one scan

In this post, we will how to find middle element of linked list in one scan.
For example
Middle element of below linked list is 4.

Middle element of linked list


Trivial algorithm

  • Find length of linked list by iterating over linked list
  • Iterate over linked list upto length/2 and get the middle element of linked list.

but we need to find middle element in one scan, here is improved version of above algorithm.


Improved algorithm

  • Initialize two pointers slowPointer and fastPointer.
  • Increment slowPoint by one node and fastPointer by two nodes.
  • Once fastPointer reaches to end of linked list, slowPointer will be at middle of linked list.

Output of above program

Linked list:
2 -> 9 -> 4 -> 1 -> 7
========================================
Middle of linked list: 4

That’s all about finding middle element of linked list.

Leave a Reply

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