Middle of a singly linked list of unknown length

[Himanshu Chauhan]

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

[Richard Tobin]

Re: Middle of a singly linked list of unknown length

In article <g2atn8$k9f$1@a ioe.org>,
Himanshu Chauhan <chauhan.jpr@gm ail.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)

[Dan]

Re: Middle of a singly linked list of unknown length

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.

[rahul]

Re: Middle of a singly linked list of unknown length

On Jun 6, 1:48 pm, Himanshu Chauhan <chauhan....@gm ail.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.

[Jens Thoms Toerring]

Re: Middle of a singly linked list of unknown length

Himanshu Chauhan <chauhan.jpr@gm ail.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.programmin g.

Regards, Jens
--
\ Jens Thoms Toerring ___ jt@toerring.de
\______________ ____________ http://toerring.de

[CBFalconer]

Re: Middle of a singly linked list of unknown length

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 **

[Kenneth Brody]

Re: Middle of a singly linked list of unknown length

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:ThisIsA SpamTrap@gmail. com>

[Bartc]

Re: Middle of a singly linked list of unknown length


"Kenneth Brody" <kenbrody@spamc op.netwrote in message
news:484954EE.D E3F5A81@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

[Keith Thompson]

Re: Middle of a singly linked list of unknown length

CBFalconer <cbfalconer@yah oo.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_Keit h) kst-u@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"

[Antoninus Twink]

Re: Middle of a singly linked list of unknown length

On 6 Jun 2008 at 16:36, Keith Thompson wrote:

CBFalconer <cbfalconer@yah oo.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.programmin g.)

[CBFalconer]

Re: Middle of a singly linked list of unknown length

Keith Thompson wrote:

CBFalconer <cbfalconer@yah oo.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 **

[Richard Tobin]

Re: Middle of a singly linked list of unknown length

In article <slrng4iqvv.co1 .nospam@nospam. invalid>,
Antoninus Twink <nospam@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)

[Eric Sosman]

Re: Middle of a singly linked list of unknown length

Antoninus Twink wrote:

On 6 Jun 2008 at 16:36, Keith Thompson wrote:

>CBFalconer <cbfalconer@yah oo.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.programmin g.)

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.programmin g where he belongs
and where he'll get better answers.

--
Eric.Sosman@sun .com

[Kenneth Brody]

Re: Middle of a singly linked list of unknown length

Bartc wrote:

>
"Kenneth Brody" <kenbrody@spamc op.netwrote in message
news:484954EE.D E3F5A81@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 "destinatio n
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:ThisIsA SpamTrap@gmail. com>

[Antoninus Twink]

Re: Middle of a singly linked list of unknown length

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.programmin g where he belongs
and where he'll get better answers.

Even the people in comp.programmin g aren't able to do the impossible.