Sunday, September 11, 2011

Find median of a linked list or a Tree

This pseudo-code holds for a Double Linked list:

1. init two pointers one at the start of the list(p1) and the other at the end (p2)
2. if p1=null or p2==null return NONE
3. At each iteration, visit node p1.next and p2.previous
4. if p1.next==p2.previous !=p1 || p2 then middle is obtained for an odd number of nodes. Return result
5. if p1.next==p2.previous=p1|| p2  then middle is  for an even number of nodes. Return result(either p1 or p2)
6. Repeat 2

This pseudo-code holds for a Single Linked list:
1. init two pointers(p1,p2) at head of the linked list
2. p2 traverses twice as fast as p1
3. For each iteration p1=p1.next and p2=p2.next.next;
4. if p2==null or p2.next=null return middle element = p1
5. Repeat Step 2

Complexity : O(n)

0 comments:

Post a Comment