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?

2 comments:

  1. lbandlavDecember 11, 2010 at 10:00 PM

    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 :)

    ReplyDelete
  2. LakshmiDecember 12, 2010 at 9:37 AM

    @Laxmi

    Yep, you are correct

    ReplyDelete