Middle of a singly linked list of unknown length

Discussion in 'C Programming' started by Himanshu Chauhan, Jun 6, 2008.

  1. 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
     
    Himanshu Chauhan, Jun 6, 2008
    #1
    1. Advertising

  2. Himanshu Chauhan

    Dan Guest


    > 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.
     
    Dan, Jun 6, 2008
    #2
    1. Advertising

  3. In article <g2atn8$k9f$>,
    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?


    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)
     
    Richard Tobin, Jun 6, 2008
    #3
  4. Himanshu Chauhan

    rahul Guest

    On Jun 6, 1:48 pm, 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?
    >
    > 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.
     
    rahul, Jun 6, 2008
    #4
  5. 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?


    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 ___
    \__________________________ http://toerring.de
     
    Jens Thoms Toerring, Jun 6, 2008
    #5
  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:>
     
    Kenneth Brody, Jun 6, 2008
    #6
  7. Himanshu Chauhan

    Bartc Guest

    "Kenneth Brody" <> wrote in message
    news:...
    > 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
     
    Bartc, Jun 6, 2008
    #7
  8. CBFalconer <> writes:
    > 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) <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"
     
    Keith Thompson, Jun 6, 2008
    #8
  9. On 6 Jun 2008 at 16:36, Keith Thompson wrote:
    > CBFalconer <> writes:

    [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.)
     
    Antoninus Twink, Jun 6, 2008
    #9
  10. In article <>,
    Antoninus Twink <> wrote:
    >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)
     
    Richard Tobin, Jun 6, 2008
    #10
  11. Bartc wrote:
    >
    > "Kenneth Brody" <> wrote in message
    > news:...
    > > 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:>
     
    Kenneth Brody, Jun 6, 2008
    #11
  12. 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.
     
    Antoninus Twink, Jun 6, 2008
    #12
  13. CBFalconer <> writes:
    > Keith Thompson wrote:
    >> CBFalconer <> writes:
    >>> 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) <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"
     
    Keith Thompson, Jun 6, 2008
    #13
  14. Himanshu Chauhan

    user923005 Guest

    On Jun 6, 1:48 am, 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?


    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.
     
    user923005, Jun 7, 2008
    #14
  15. Himanshu Chauhan

    Richard Bos Guest

    CBFalconer <> wrote:

    > 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
     
    Richard Bos, Jun 9, 2008
    #15
  16. On Tue, 10 Jun 2008 22:53:03 -0700, "Chris Thomasson" <>
    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
     
    Kevin D. Quitt, Jun 13, 2008
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patrick McCourt

    Stack & Singly Linked List Data Structures

    Patrick McCourt, May 24, 2004, in forum: Java
    Replies:
    2
    Views:
    964
    Kenneth P. Turvey
    May 24, 2004
  2. HS-MOON
    Replies:
    4
    Views:
    627
    Method Man
    Sep 24, 2004
  3. CR

    AlphaSort for singly linked list

    CR, Dec 15, 2003, in forum: C Programming
    Replies:
    1
    Views:
    528
    CBFalconer
    Dec 15, 2003
  4. RAJASEKHAR KONDABALA

    Reverse search in a singly-linked list

    RAJASEKHAR KONDABALA, Dec 24, 2003, in forum: C Programming
    Replies:
    20
    Views:
    5,882
    saadbinsaulat
    Feb 27, 2011
  5. Anando

    pruning a linear singly linked list

    Anando, Apr 23, 2006, in forum: C Programming
    Replies:
    59
    Views:
    1,306
    Richard Bos
    Apr 28, 2006
Loading...

Share This Page