• 03-31-2005, 09:27 AM
Bhavna
quest: find midlle element of a linked list in one traversal.
I have one soln. but i dnt think that goes in one traversal
it is
first=list;
sec=list;
while(sec->next != NULL)
{
first=first->next;
sec=sec->next->next;
}
cout<<first->val;

As when we are checking sec->next we are accessing linked list . and by incrementing first=first->next we are also traversing LL . so its not parrallel working not a single traversal

Any other soln.
• 03-31-2005, 10:13 AM
drkybelk
Hi,

do you mean the n-th element in a list of length 2*n-1? the solution could be something like:
set pointer p1 to the beginning of the list
set pointer p2 to the end of the list
iteratively set p1 to p1->next und p2 to p2->prev until p1 == p2
Tat won't work of course, if the number of elements in your list is even, but it would work in 1 iteration.
Cheers,

Dieter
• 03-31-2005, 05:17 PM
jonnin
its trivial for a doubly linked list, but for a singly linked list?
You need to know how many you have, but if you don't maintain that, how to do it?