473,378 Members | 1,426 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,378 software developers and data experts.

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 37470
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,426 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

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

Similar topics

4
by: HS-MOON | last post by:
I'm asking you to help me. I'm a beginner of studying c++. I'm trying to make the Singly Linked List(Ordered). Anyway, I've been debugging all day. I can't sort it out!! As you see, I don't...
19
by: RAJASEKHAR KONDABALA | last post by:
Hi, Does anybody know what the fastest way is to "search for a value in a singly-linked list from its tail" as oposed to its head? I am talking about a non-circular singly-linked list, i.e.,...
13
by: Raj | last post by:
Is there any way to delete a particular node from a singly linked list where the header of the list is unknown.Only pointer available is the one which points to the node to be deleted
3
by: malik | last post by:
// Linked Lists in classes(excluding structures) without using tail pointer # include<iostream.h> # include<stdlib.h> void Swap(int num1, int num2) { int a = num1; num2 = num1; num2 = a;
0
by: magic9baller | last post by:
I have to use bubblesort to sort a singly linked list. (Yes I am a n00b.) The tricky part is that I have to move pointers rather than moving the contents of one node to the other. I think my problem...
10
by: Aditya | last post by:
Hi All, I would like to know how it is possible to insert a node in a linked list without using a temp_pointer. If the element is the first element then there is no problem but if it is in...
23
by: Himanshu Chauhan | last post by:
Hi! I was wondering, In the first parse of a singly linked list of unknown length, is it possible to know when we are at middle of the linked list? Regards --Himanshu
7
by: davidson1 | last post by:
Hello friends, I want ur help regarding singly linked list in C,I tried in net,But it is confusing and difficult.I want singly linked list in a simple way of Understanding.Please Help Me I want...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.