While the other answers work, the question was to find the middle node with a single iteration. I will assume you are using a self-written linked list class. If so, the following function would have to be a member of that class. This returns the data in the middle node, but it shouldn't be too difficult to adapt it to return a pointer to the the node, or whatever else you want to do with the middle node. First here are some explanations about the function:
"Type" is whatever data type your list holds,
"nodeType" is whatever you named the node class you're list uses.
"link" is the node member pointer that points to the next node,
"info" is the node member containing the data.
"first" is the list's pointer to the first node.
- Type& findMiddleNode()
-
{
-
int check = 0;
-
nodeType *current;
-
nodeType *mid;
-
-
current = first;
-
mid = first;
-
-
while (current != NULL)
-
{
-
current = current->link;
-
check = (check + 1) % 2;
-
-
if (check == 0)
-
mid = mid->link;
-
}
-
-
return mid->info;
-
}
Note: This will cause errors if there list is empty
The basic concept of this function is to iterate through the list once, but with 2 pointers. But one pointer is only moved every other time.
Also, if the list has an even amount of nodes, this will return the one closer to the beginning of the list.