How to find middle node of singly linked list in c

[vikaskumaragrawal]

hi friends, i have a question plz help me. my question is ...
how can i find middle node of linked list in single traverse???????

[Silent1Mezzo]

hi friends, i have a question plz help me. my question is ...
how can i find middle node of linked list in single traverse???????

Go through the entire linked list incrementing a counter each time. Then with that counter you'll know exactly where the middle is (assuming no nodes have been inserted between the first time you go through it and when you check for the middle)

[sicarie]

I'd iterate through, count each node, and then half that count.

[Silent1Mezzo]

I'd iterate through, count each node, and then half that count.

Sweet! Finally beat a mod to it.

[ssorower]

Just to add litte more, if you want copy of the middle node in a single traverse (insted of the middle node position only), what you may do is, always have an updated copy of the middle node every time you increase the value of the counter starting at first node.

For example, you can have two node variables to have middle node values, let mid1 and mid2 (in case of even number of total nodes you will have two middle nodes). Now when you visit the first node (i.e. I assume counter =1) then copy this as mid1. then when counter =2 then copy this as mid2. Now every time you get an odd count, you can move the mid1 one data forward to have the middle node and at just succeeding step when you find an even count, you can move the mid2 one data forward.

In this way, you will always have a copy of middle node and by the time you finish a single traverse you will have the middle node copied in mid1 (if total count is odd), or copied in mid1 and mid2 (if total count is even).

Sorry for little bit complex description :)

--Sorower

[phiefer3]

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.

[sicarie]

While the other answers work, the question was to find the middle node with a single iteration.

Oh yeah, I didn't consider that the value of the node needed to be returned - the OP didn't say anything about getting the value, just figuring out which node was in the middle.

Very nice!

[JosAH]

Have two pointers iterate over that list; call them 'slow' and 'fast'. The slow pointer
hops over one element in one loop pass; the fast pointer attempts to hop over
two elements of your list. When the fast pointer fails to hop, the slow pointer
points to the 'middle' element of the list. Mind the quotes because a list with an
even number of elements doesn't have a 'middle' element.

kind regards,

Jos

[vikaskumaragrawal]

Have two pointers iterate over that list; call them 'slow' and 'fast'. The slow pointer
hops over one element in one loop pass; the fast pointer attempts to hop over
two elements of your list. When the fast pointer fails to hop, the slow pointer
points to the 'middle' element of the list. Mind the quotes because a list with an
even number of elements doesn't have a 'middle' element.

kind regards,

Jos

thnx JosAH ur idea is very good

[bheemashankargh]

hi friends, i have a question plz help me. my question is ...
how can i find middle node of linked list in single traverse???????

::Code removed per Posting Guidelines, perhaps an algorithm would be more helpful?::

this will u give d mid element from a linked list in a single traversal
also

[samoak]

@JosAH
---
This method only ensures that after a successful alternation of slow and fast pointers, the slow pointer is just a node away from the fast one.

[JosAH]

@samoak
Check again: the 'slow' pointer hops over one element at every loop pass while the 'fast' pointer hops over two elements at every loop pass.

btw, this is a very old (dead) thread.

kind regards,

Jos

[R Suresh Kumar]

It is simple..
1) Just go to the end of the list..
2) Here you will have the address of the last node.
3) By incrementing the counter you can find the length of the list.
4) if the list length is 10, (last node address-10/2)will give the address of the middle node

[donbock]

This is a very old thread, the OP was apparently satisfied that the question had been answered.

By the way, your suggestion only works if the list nodes are allocated in a contiguous block of memory and that links never point backwards. That is, your suggestion only works for an array.

[srinivasulu A]

typedef struct node
{
int info;
struct node *link;
}NODE;

NODE *p1=NULL; //for returning middle node info.

NODE *retunrmid(NODE *start)
{
NODE *p2=start;
p1=start;
while((p2->link!=NULL) && (p2->link->link!=NULL))
{
p2=p2->link->link;
printf("link->link:%d\n",p2->info); //just for referene
p1=p1->link;
}

printf("returned info:%d\n",p1->info); //reference for middle node.
return p1;
}