469,268 Members | 920 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,268 developers. It's quick & easy.

How to find middle node of singly linked list in c

hi friends, i have a question plz help me. my question is ...
how can i find middle node of linked list in single traverse???????
Jun 29 '07 #1
14 37048
Silent1Mezzo
208 100+
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)
Jun 29 '07 #2
sicarie
4,677 Expert Mod 4TB
I'd iterate through, count each node, and then half that count.
Jun 29 '07 #3
Silent1Mezzo
208 100+
I'd iterate through, count each node, and then half that count.
Sweet! Finally beat a mod to it.
Jun 29 '07 #4
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
Jun 29 '07 #5
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.

Expand|Select|Wrap|Line Numbers
  1. Type& findMiddleNode()
  2. {
  3.     int check = 0;
  4.     nodeType *current;
  5.     nodeType *mid;
  6.  
  7.     current = first;
  8.     mid = first;
  9.  
  10.     while (current != NULL)
  11.     {
  12.         current = current->link;
  13.         check = (check + 1) % 2;
  14.  
  15.         if (check == 0)
  16.             mid = mid->link;
  17.     }
  18.  
  19.     return mid->info;
  20. }
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.
Jun 29 '07 #6
sicarie
4,677 Expert Mod 4TB
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!
Jun 29 '07 #7
JosAH
11,448 Expert 8TB
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
Jun 29 '07 #8
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
Jul 5 '07 #9
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
Oct 31 '07 #10
samoak
1
@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.
May 16 '09 #11
JosAH
11,448 Expert 8TB
@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
May 16 '09 #12
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
Oct 25 '10 #13
donbock
2,422 Expert 2GB
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.
Oct 25 '10 #14
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;
}
Apr 10 '15 #15

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

4 posts views Thread by HS-MOON | last post: by
19 posts views Thread by RAJASEKHAR KONDABALA | last post: by
23 posts views Thread by Himanshu Chauhan | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.