Linked List

[NitinLinx]

This was a question from GE interview when faced the GE interview..
Question : There is a one linked List with known starting and ending, you have to find out the middle of the linked list, you can traverse the whole linked list at once only....

[AdrianH]

This was a question from GE interview when faced the GE interview..
Question : There is a one linked List with known starting and ending, you have to find out the middle of the linked list, you can traverse the whole linked list at once only....

That is easy, but unfortunately I don't think that we can give you the answer. It might be against policy. What do you other moderators think?


Adrian

[DeMan]

(Not that I'm a moderator....but) I can't see that there's any harm discussing the method........

The middle of a list is halfway from the start to the finish (obvious I know, but this is quite significant)

I will assume that traversing the list once only means "you can only use one loop", not "you can only use one pointer"

Step through the list:
Pseudocode:

counter == 0;
this.element = first.element;
mid.element=this.element;
while(this.element != last.element)
{
   counter++;
  if(counter % 2 == 0)
  {
    mid = mid.next();
  }
  this = this.next();
}
 

If there is 1 item, mid is correct, if there is an even number of items, thelater item is found, if there is an odd number, the middle is found (I think)

[DeMan]

And I probably shouldn't have used "this".......so call it "current" if you like

[sabitha]

Hi,

There is another solution for the same...

Use 2 pointers p1 and p2, initially both should point to the head.
Advance p1... one node at a time
Advance p2... two node at a time.
When p2 reaches the end, p1 is in the middle.

Thanks
Saby Abraham

[Sreenivas Gangadhar]

This was a question from GE interview when faced the GE interview..
Question : There is a one linked List with known starting and ending, you have to find out the middle of the linked list, you can traverse the whole linked list at once only....

Hi, i hope this works, because the starting and ending of the linked list is known one can traverse the list from either side, with a counter, thus same counter and the value at the pointer then break the loop. thus answer is out in 1/2 of the recurring loop with two pointers pointing either side of the linked list.

[DeMan]

Assuming it's a doubly linked list you could take the "let's meet in (near) the middle).
Knowing the start and end, however (even in a doubly linked list), doesn't help us to know how many elemetns are in between.....