473,289 Members | 1,848 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,289 software developers and data experts.

Middle of a singly linked list of unknown length

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
Jun 27 '08 #1
23 4319
In article <g2**********@aioe.org>,
Himanshu Chauhan <ch*********@gmail.comwrote:
>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?
Obviously not, since nothing would be different if extra elements were
added to the end.

-- Richard
--
In the selection of the two characters immediately succeeding the numeral 9,
consideration shall be given to their replacement by the graphics 10 and 11 to
facilitate the adoption of the code in the sterling monetary area. (X3.4-1963)
Jun 27 '08 #2
Dan
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?
You could do it if you kept track of how many were in the list when you
built it.
Jun 27 '08 #3
On Jun 6, 1:48 pm, Himanshu Chauhan <chauhan....@gmail.comwrote:
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
You can keep the count of nodes inserted as a static or global
variable. By counting
the number of iterations, you can decide if you are in the middle of
the list.

Just out of curiosity, this question is meant for some real code or is
it just like that.
Jun 27 '08 #4
Himanshu Chauhan <ch*********@gmail.comwrote:
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?
Are you looking for the old trick of using two pointers, the first
one always getting set to the next element, the other one being set
to the successor of the next element so, when the second pointer
reaches the end of the list, the first one points to the middle
element? But I don't know if that is allowed by what you call
"first parse".

BTW, this hasn't anything to do with C, so such a question is
much better suited for comp.programming.

Regards, Jens
--
\ Jens Thoms Toerring ___ jt@toerring.de
\__________________________ http://toerring.de
Jun 27 '08 #5
Himanshu Chauhan wrote:
>
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?
Yes. Just build the list in two halves, and join them when
building is done. The head of the second half will be the
midpoint, withing an error of one.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **
Jun 27 '08 #6
Himanshu Chauhan wrote:
>
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?
The me rephrase the problem, and see if you can find a solution:

Drive down this road and stop halfway to a destination which I
have not yet revealed.

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>

Jun 27 '08 #7

"Kenneth Brody" <ke******@spamcop.netwrote in message
news:48***************@spamcop.net...
Himanshu Chauhan wrote:
>>
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?

The me rephrase the problem, and see if you can find a solution:

Drive down this road and stop halfway to a destination which I
have not yet revealed.
That's not quite the same. In that case you would not know when you got to
the destination so it's unsolveable. A linked list however has a definite
end point, assuming it's not circular.

Better, 'stop halfway to the end of the road of unknown length'. Easily done
by traversing the entire length one and a half times.
--
Bartc
Jun 27 '08 #8
CBFalconer <cb********@yahoo.comwrites:
Himanshu Chauhan wrote:
>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?

Yes. Just build the list in two halves, and join them when
building is done. The head of the second half will be the
midpoint, withing an error of one.
Right, finding a solution is easy if you're allowed to redefine the
problem.

The problem statement assumed "a singly linked list of unknown
length", not two lists of equal length.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Jun 27 '08 #9
On 6 Jun 2008 at 16:36, Keith Thompson wrote:
CBFalconer <cb********@yahoo.comwrites:
[snip nonsense]
>
Right, finding a solution is easy if you're allowed to redefine the
problem.
Vintage CBF. At least two people have already provided a correct
solution (i.e. run two pointers through the list, one travelling at
half the speed of the other), but several hours later in wades Chuck
with something completely wrong-headed. (Still, I suppose at least he
tried, albeit unsuccessfully, to answer the damn question for once,
instead of telling the OP to get lost and try comp.programming.)

Jun 27 '08 #10
Keith Thompson wrote:
CBFalconer <cb********@yahoo.comwrites:
>Himanshu Chauhan wrote:
>>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?

Yes. Just build the list in two halves, and join them when
building is done. The head of the second half will be the
midpoint, withing an error of one.

Right, finding a solution is easy if you're allowed to redefine
the problem.

The problem statement assumed "a singly linked list of unknown
length", not two lists of equal length.
To have the single list, you have to form it, by adding one item at
a time. The break into two portions does this. If you don't like
having two lists during formation, just have one, and add items
alternately before the 'middle' and at the 'end'.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
** Posted from http://www.teranews.com **
Jun 27 '08 #11
In article <sl*******************@nospam.invalid>,
Antoninus Twink <no****@nospam.invalidwrote:
>At least two people have already provided a correct
solution (i.e. run two pointers through the list, one travelling at
half the speed of the other)
That's not a solution to the problem as I interpreted it. It uses
one-and-a-half passes over the list, rather than stopping in the
middle during the first pass.

-- Richard
--
In the selection of the two characters immediately succeeding the numeral 9,
consideration shall be given to their replacement by the graphics 10 and 11 to
facilitate the adoption of the code in the sterling monetary area. (X3.4-1963)
Jun 27 '08 #12
Antoninus Twink wrote:
On 6 Jun 2008 at 16:36, Keith Thompson wrote:
>CBFalconer <cb********@yahoo.comwrites:
[snip nonsense]
>Right, finding a solution is easy if you're allowed to redefine the
problem.

Vintage CBF. At least two people have already provided a correct
solution (i.e. run two pointers through the list, one travelling at
half the speed of the other),
I think those so-called solutions are ruled out by the
O.P.'s requirement to get the answer "in the first parse"
over the list, which I read as a garbled form of "in the
first pass" over the list. Using two pointers means using
one-and-a-half passes.
Still, I suppose at least he tried, albeit unsuccessfully, to
answer the damn question for once, instead of telling the OP
to get lost and try comp.programming.)
Right, that was a mistake on his part. Chuck, I hereby
chastise you for answering an off-topic question instead of
sending the questioner to comp.programming where he belongs
and where he'll get better answers.

--
Er*********@sun.com
Jun 27 '08 #13
Bartc wrote:
>
"Kenneth Brody" <ke******@spamcop.netwrote in message
news:48***************@spamcop.net...
Himanshu Chauhan wrote:
>
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?
The me rephrase the problem, and see if you can find a solution:

Drive down this road and stop halfway to a destination which I
have not yet revealed.

That's not quite the same. In that case you would not know when you got to
the destination so it's unsolveable. A linked list however has a definite
end point, assuming it's not circular.
Perhaps I should have included my implied: "I'll tell you when you
get to the end." (Just as a singly-linked list has a "destination
not yet revealed" until you reach the end.)
Better, 'stop halfway to the end of the road of unknown length'.
Same thing.
Easily done by traversing the entire length one and a half times.
Which doesn't qualify as "first parse['pass'?]" as stated by the OP.

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>

Jun 27 '08 #14
On 6 Jun 2008 at 17:55, Eric Sosman wrote:
I think those so-called solutions are ruled out by the O.P.'s
requirement to get the answer "in the first parse" over the list,
which I read as a garbled form of "in the first pass" over the list.
Using two pointers means using one-and-a-half passes.
[snip]

I interpreted the OP's requirement as a garbled form of an old chestnut
textbook exercise.
>
Chuck, I hereby chastise you for answering an off-topic question
instead of sending the questioner to comp.programming where he belongs
and where he'll get better answers.
Even the people in comp.programming aren't able to do the impossible.

Jun 27 '08 #15
CBFalconer <cb********@yahoo.comwrites:
Keith Thompson wrote:
>CBFalconer <cb********@yahoo.comwrites:
>>Himanshu Chauhan wrote:
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?

Yes. Just build the list in two halves, and join them when
building is done. The head of the second half will be the
midpoint, withing an error of one.

Right, finding a solution is easy if you're allowed to redefine
the problem.

The problem statement assumed "a singly linked list of unknown
length", not two lists of equal length.

To have the single list, you have to form it, by adding one item at
a time. The break into two portions does this. If you don't like
having two lists during formation, just have one, and add items
alternately before the 'middle' and at the 'end'.
I still say you're changing the requirements.

You can also keep track of the number of items in the list as you
create it, or you can store the nodes of the linked list in a
contiguous array, either of which makes it possible to find the middle
without traversing the whole thing.

But the problem as stated referred to "a singly linked list of unknown
length", presumably one given to you by some outside source.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Jun 27 '08 #16
"Himanshu Chauhan" <ch*********@gmail.comwrote in message
news:g2**********@aioe.org...
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?
Does "first parse" mean 1 pass through the _entire_ list? If so, then I
guess you could do something like this:

<pseudo-code sketch / error checking omitted>
__________________________________________________ ______________
struct slist {
struct slist* next;
};

#define CHUNK 32
#define GROWBY 2

static struct slist*
slist_get_middle_on_one_iteration(
struct slist* _this
) {
size_t i = 0;
size_t nl = CHUNK;
struct slist* nodes = malloc(sizeof(*nodes) * nl);
while (_this) {
if (i >= nl) {
nl *= GROWBY;
nodes = realloc(nodes, sizeof(*nodes) * nl);
}
nodes[i++] = _this;
_this = _this->next;
}
if (i) {
_this = nodes[i / 2];
}
free(nodes);
return _this;
}
__________________________________________________ ______________

Is that anywhere near what your looking for?

Jun 27 '08 #17
On Jun 6, 1:48*am, Himanshu Chauhan <chauhan....@gmail.comwrote:
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?
No. The obvious solution is to add a length element to the head of
your list.

I don't think I have ever used linked lists without list lengths.

I want to know how many things are in my list all the time (though I
rarely will want to know if something is the middle item or not).

Here is a list with a counter:
http://mij.oltrelinux.com/devel/simclist/

I'm a lot more likely to use a skiplist than a singly linked list:
http://sourceforge.net/projects/skiplist/

Memory cost is similar and they are better if you ever have to find
something in it. Most of the time, you will.
Jun 27 '08 #18
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:e-******************************@comcast.com...
"Himanshu Chauhan" <ch*********@gmail.comwrote in message
news:g2**********@aioe.org...
>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?

Does "first parse" mean 1 pass through the _entire_ list? If so, then I
guess you could do something like this:

<pseudo-code sketch / error checking omitted>
__________________________________________________ ______________
struct slist {
struct slist* next;
};

#define CHUNK 32
#define GROWBY 2

static struct slist*
slist_get_middle_on_one_iteration(
struct slist* _this
) {
size_t i = 0;
size_t nl = CHUNK;
struct slist* nodes = malloc(sizeof(*nodes) * nl);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^

I got the size wrong! Here is correction:

struct slist* nodes = malloc(sizeof(nodes) * nl);

while (_this) {
if (i >= nl) {
nl *= GROWBY;
nodes = realloc(nodes, sizeof(*nodes) * nl);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^

Ditto:
nodes = realloc(nodes, sizeof(nodes) * nl);

Sorry about that.
}
nodes[i++] = _this;
_this = _this->next;
}
if (i) {
_this = nodes[i / 2];
}
free(nodes);
return _this;
}
__________________________________________________ ______________

Is that anywhere near what your looking for?
Jun 27 '08 #19
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:e-******************************@comcast.com...
"Himanshu Chauhan" <ch*********@gmail.comwrote in message
news:g2**********@aioe.org...
>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?

Does "first parse" mean 1 pass through the _entire_ list? If so, then I
guess you could do something like this:

<pseudo-code sketch / error checking omitted>
__________________________________________________ ______________
struct slist {
struct slist* next;
};

#define CHUNK 32
#define GROWBY 2

static struct slist*
slist_get_middle_on_one_iteration(
struct slist* _this
) {
size_t i = 0;
size_t nl = CHUNK;
struct slist* nodes = malloc(sizeof(*nodes) * nl);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^

ARGH! I want an array of slist pointers, NOT slist objects!

struct slist** nodes = malloc(sizeof(*nodes) * nl);

while (_this) {
if (i >= nl) {
nl *= GROWBY;
nodes = realloc(nodes, sizeof(*nodes) * nl);
}
nodes[i++] = _this;
_this = _this->next;
}
if (i) {
_this = nodes[i / 2];
}
free(nodes);
return _this;
}
__________________________________________________ ______________

Is that anywhere near what your looking for?



Here is some code which compiles:
__________________________________________________ ______________
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct slist {
struct slist* next;
};
#define CHUNK 32
#define GROWBY 2
static struct slist*
slist_get_middle_on_one_iteration(
struct slist* _this
) {
size_t i = 0;
size_t nl = CHUNK;
struct slist** nodes = malloc(sizeof(*nodes) * nl);
if (nodes) {
while (_this) {
if (i >= nl) {
struct slist** new_nodes;
nl *= GROWBY;
new_nodes = realloc(nodes, sizeof(*new_nodes) * nl);
if (! new_nodes) {
free(nodes);
return NULL;
}
nodes = new_nodes;
}
nodes[i++] = _this;
_this = _this->next;
}
if (i) {
_this = nodes[i / 2];
}
free(nodes);
return _this;
}
return NULL;
}
int main(void) {
struct slist nodes[5];
struct slist* middle;
nodes[0].next = nodes + 1;
nodes[1].next = nodes + 2;
nodes[2].next = nodes + 3;
nodes[3].next = nodes + 4;
nodes[4].next = NULL;
middle = slist_get_middle_on_one_iteration(nodes);
assert(middle == nodes + 2);
puts("\n\npress <ENTERto exit...");
getchar();
return 0;
}

__________________________________________________ ______________


DAMN IT!
;^(...

Jun 27 '08 #20
CBFalconer <cb********@yahoo.comwrote:
Keith Thompson wrote:
The problem statement assumed "a singly linked list of unknown
length", not two lists of equal length.

To have the single list, you have to form it,
Not true; someone else may have formed it for you.

And that's just the _trivial_ objection to your solution.

Richard
Jun 27 '08 #21
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:ms******************************@comcast.com. ..
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:e-******************************@comcast.com...
>"Himanshu Chauhan" <ch*********@gmail.comwrote in message
news:g2**********@aioe.org...
>>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?

Does "first parse" mean 1 pass through the _entire_ list? If so, then I
guess you could do something like this:
[...]
Here is some code which compiles:
__________________________________________________ ______________
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct slist {
struct slist* next;
};
#define CHUNK 32
#define GROWBY 2
static struct slist*
slist_get_middle_on_one_iteration(
struct slist* _this
) {
size_t i = 0;
size_t nl = CHUNK;
struct slist** nodes = malloc(sizeof(*nodes) * nl);
if (nodes) {
while (_this) {
if (i >= nl) {
struct slist** new_nodes;
nl *= GROWBY;
new_nodes = realloc(nodes, sizeof(*new_nodes) * nl);
if (! new_nodes) {
free(nodes);
return NULL;
}
nodes = new_nodes;
}
nodes[i++] = _this;
_this = _this->next;
}
if (i) {
_this = nodes[i / 2];
}
free(nodes);
return _this;
}
return NULL;
}
int main(void) {
struct slist nodes[5];
struct slist* middle;
nodes[0].next = nodes + 1;
nodes[1].next = nodes + 2;
nodes[2].next = nodes + 3;
nodes[3].next = nodes + 4;
nodes[4].next = NULL;
middle = slist_get_middle_on_one_iteration(nodes);
assert(middle == nodes + 2);
puts("\n\npress <ENTERto exit...");
getchar();
return 0;
}

__________________________________________________ ______________

Humm... I think I just did somebody's homework!

DAMN IT!
;^(...
Jun 27 '08 #22
On Tue, 10 Jun 2008 22:53:03 -0700, "Chris Thomasson" <cr*****@comcast.net>
wrote:
>Humm... I think I just did somebody's homework!
Probably. I didn't look at your code, but it looks more complex than what
I was thinking: Two pointers start at the head. Each time you move one of
the two, more the other one just one.

--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Jun 27 '08 #23
"Kevin D. Quitt" <KQ****@IEEInc.comwrote in message
news:nv********************************@4ax.com...
On Tue, 10 Jun 2008 22:53:03 -0700, "Chris Thomasson"
<cr*****@comcast.net>
wrote:
>>Humm... I think I just did somebody's homework!

Probably. I didn't look at your code, but it looks more complex than what
I was thinking: Two pointers start at the head. Each time you move one
of
the two, more the other one just one.
You mean something like:
A->B->C->D->E->NULL / The middle is node C

Iteration
____________________
1: cur = A;
2: middle = A;

3: cur = B;
4: cur = C;
5: middle = B;

6: cur = D;
7: cur = E;
8: middle = C; /*** GOT IT! ***/

That works but I am not sure it "strictly" adheres to the rules as-is. I
guess one could argue that your actually making one-and-a-half parses; not
just one. The `cur' pointer constitutes a full parse, while the `middle'
pointer represents half a parse. See, it took 8 links to parse a list of 5
nodes. The solution I hacked together can solve this problem using only 5
links. This is how I understand the rules. Perhaps I am missing something
here...
Any thoughts?

Jun 27 '08 #24

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

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.,...
7
by: Shwetabh | last post by:
Hi, can some one tell me: -> how to remove a loop from a singly linked list with a loop. -> how to count the number of nodes in a looped singly link list. Thanks
3
by: Little | last post by:
Could someone help me get started on this program or where to look to get information, I am not sure how to put things together. 1. Create 4 double linked lists as follows: (a) A double linked...
1
by: Little | last post by:
Could someone help me figure out how to put my project together. I can't get my mind wrapped around the creation of the 4 double Linked Lists. Thank your for your insight. 1. Create 4 double...
3
by: Little | last post by:
Could someone tell me what I am doing wrong here about declaring mutiple double linked lists. This is what the information is for the project and the code wil be below that. Thank your soo much for...
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
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...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...

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.