10 December 2010

Puzzle - Which is at the Middle

There is a linked list (you can assume that it is unidirectional or bi-directional). The list is not ordered in any specific format (unsorted).
  • What are the methods (or ways) by which you find the middle element of the list? (For example, if the element has 11 elements, 6th element is the middle. If you have 10 elements, 5th or 6th (whichever you like) is the middle element of the list).
  • What is algorithmic complexity of each method?


lbandlav said...

take 2 pointers initially pointing to the head, increment the pointer p1 twice with proper null checks and increment the p2 once, when the pointer p1 points to the last element of the list, p2 points to the middle element. complexity is O(n)

Let me know if am wrong :)

Lakshmi Narayanan N said...


Yep, you are correct