DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Mar 2005
Posts
1

## Linked list problem

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.

2. Registered User
Join Date
Jan 2005
Location
UK
Posts
604
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

3. Senior Member
Join Date
Dec 2003
Posts
3,366
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...
Last edited by jonnin; 03-31-2005 at 05:31 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise
 Questions? Contact us. C++ Web Development Wireless Latest Tips Open Source

×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.