Printable View
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.
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
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?
start two pointers at 'head'
now you just increment two to one. Every time you advance the main pointer forward two nodes, advance the other pointer one node. When the main pointer hits 'null', your other pointer points to the element in the middle. (n/2 rounded down for even lists)
The problem is unrealistic because if you needed the middle element, you would maintain a pointer to it or a count of the nodes so you could just go 1/2 way. Linked lists are so slow... I have not used one since school...
