Tuesday, March 30, 2010

how to find out middle element of a linked list in a single traversal

program:

Node* findMidNode(Node* start)
{
Node* midNode = start;
while(start != NULL || start->next != NULL)
{
midNode = midNode->next;
start = start->next->next;
}
return midNode;
}

Algorithm
:

midNode is pointing to next of the midNode in every iteration and
start is pointing to next to next (i.e., increment 2) of start in every iteration.
so, when start is at the end, then midNode is pointing to middle element of the List.

No comments: