Data Structures/Algorythms-Help 2!?

Question

You have a two-way list (that you can move back and farwards in it).you have three pointers to three different members in this list.
Suggest an algorythm that says which pointer points to the middle of the numbers. For example ,if the pointed numbers are 1 ,6 and 10 ,the agorythm will return 6.
Also you can't mark any other numbers in this list.

Answer 1

I believe that the problem is about finding out the relative positions of the three nodes in a doubly linked list and ordering them as left, middle and right.

Lets assume that a node looks like this:

typedef struct {
struct node *left;
struct node *right;
} node;

Lets say that the given 3 pointers are arbitrarily assigned as LEFT, MIDDLE and RIGHT as follows.
node *LEFT = pointer1;
node *MIDDLE = pointer2;
node *RIGHT = pointer3;

Lets also assume that the linked list is null-terminated. Lets also make the assumption that we have a swap function to swap two pointers.

Now if our assumption that whatever pointer that we have assigned as the LEFT pointer is correct, then we shall not encounter the MIDDLE and RIGHT pointers when we traverse the list in the left direction till we encounter NULL.

Suppose we meet either of the pointers, then it means that our initial assumption is not correct and we shall swap the LEFT with MIDDLE/RIGHT pointers that we encounter, and keep traveling left till we meet NULL.

The above step ensures that at the end of one traversal to the left, we have the correct pointer in the LEFT pointer. Now we have to make sure that the MIDDLE/RIGHT pointers are correct.

So we repeat the above step by starting with the MIDDLE pointer and traveling towards the LEFT pointer. If we encounter RIGHT pointer in the middle then we swap them.

Now we have the LEFT/MIDDLE/RIGHT pointers in the correct order.

for(node *iter = LEFT->left;iter != NULL; iter=iter->left) {
if(iter == MIDDLE) {
swap(LEFT, MIDDLE);
}
else if(iter == RIGHT) {
swap(LEFT, RIGHT);
}
}

for(node *iter = MIDDLE->left;iter != LEFT; iter=iter->left) {
if(iter == RIGHT) {
swap(MIDDLE, RIGHT);
break;
}
}

Answer 2

If all you need is value comparison, then it is straightforward.

If the 3 ptrs are p1,p2 & p3,

find the pseudo code below

a = p1->value;
b = p2->value;
c = p3->value;

//Check if a is the mid: It could be b-a-c or c-a-b
if((a>=b&&a<=c) || (a>=c && a<=b))
return p1;
//If b is the mid: a-b-c or c-b-a
else if ((b>=a && b<=c) || (b>=c && b<=a))
return p2;
else return p3;

If you need position comparison then you need to have pointer manipulations.