linked list question

Discussion in 'C Programming' started by junky_fellow@yahoo.co.in, Jan 22, 2008.

  1. Guest

    Hi,

    Is there any efficient way of finding the intesection point of two
    singly linked lists ?
    I mean to say that, there are two singly linked lists and they meet at
    some point. I want to find out the addres of the node where the two
    linked intersect.

    thanks for any help...
     
    , Jan 22, 2008
    #1
    1. Advertising

  2. <> wrote in message
    news:...
    > Hi,
    >
    > Is there any efficient way of finding the intesection point of two
    > singly linked lists ?
    > I mean to say that, there are two singly linked lists and they meet at
    > some point. I want to find out the addres of the node where the two
    > linked intersect.
    >
    > thanks for any help...


    you mean point of merge of linked list ? i cannot imaging "intersection" of
    singly linked

    p = listA;
    q = listB;

    while(p && q) {
    if(p->next == q->next) break;
    p = p->next;
    q = q->next;
    }

    if(p && q && (p->next == q->next))
    {
    printf("Merging point found\n");
    }

    But careful: I have not tested the code !
     
    Ravishankar S, Jan 22, 2008
    #2
    1. Advertising

  3. Ravishankar S said:

    <snip>

    > you mean point of merge of linked list ? i cannot imaging "intersection"
    > of singly linked
    >
    > p = listA;
    > q = listB;
    >
    > while(p && q) {
    > if(p->next == q->next) break;
    > p = p->next;
    > q = q->next;
    > }
    >
    > if(p && q && (p->next == q->next))
    > {
    > printf("Merging point found\n");
    > }
    >
    > But careful: I have not tested the code !


    Indeed. Consider these linked lists:

    listA: A -- B -- C -- D
    \
    E -- F -- G
    /
    listB: H -- I

    You compare A with H, B with I, C with E, D with F, E with G. Now the loop
    stops, and q is NULL. You missed the merge point completely.

    I believe this has to be done in two nested loops (or at least, "as if" it
    were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
    be delighted to be proved wrong.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Jan 22, 2008
    #3
  4. Richard Heathfield <> writes:

    > Ravishankar S said:
    >
    > <snip>
    >
    > > you mean point of merge of linked list ? i cannot imaging "intersection"
    > > of singly linked
    > >
    > > p = listA;
    > > q = listB;
    > >
    > > while(p && q) {
    > > if(p->next == q->next) break;
    > > p = p->next;
    > > q = q->next;
    > > }
    > >
    > > if(p && q && (p->next == q->next))
    > > {
    > > printf("Merging point found\n");
    > > }
    > >
    > > But careful: I have not tested the code !

    >
    > Indeed. Consider these linked lists:
    >
    > listA: A -- B -- C -- D
    > \
    > E -- F -- G
    > /
    > listB: H -- I
    >
    > You compare A with H, B with I, C with E, D with F, E with G. Now the loop
    > stops, and q is NULL. You missed the merge point completely.
    >
    > I believe this has to be done in two nested loops (or at least, "as if" it
    > were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
    > be delighted to be proved wrong.


    You can do O(listAnodecount+listBnodecount) if you accept to allocate
    memory in O(listAnodecount+listBnodecount) as well: build reversed lists
    referencing the original and then iterate on them until they diverge.

    --
    Jean-Marc
     
    Jean-Marc Bourguet, Jan 22, 2008
    #4
  5. Guest

    On Jan 22, 9:42 am, Richard Heathfield <> wrote:
    > Ravishankar S said:
    >
    > <snip>
    >
    >
    >
    > > you mean point of merge of linked list ? i cannot imaging "intersection"
    > > of singly linked

    >
    > > p = listA;
    > > q = listB;

    >
    > > while(p && q) {
    > > if(p->next == q->next) break;
    > > p = p->next;
    > > q = q->next;
    > > }

    >
    > > if(p && q && (p->next == q->next))
    > > {
    > > printf("Merging point found\n");
    > > }

    >
    > > But careful: I have not tested the code !

    >
    > Indeed. Consider these linked lists:
    >
    > listA: A -- B -- C -- D
    > \
    > E -- F -- G
    > /
    > listB: H -- I
    >
    > You compare A with H, B with I, C with E, D with F, E with G. Now the loop
    > stops, and q is NULL. You missed the merge point completely.
    >
    > I believe this has to be done in two nested loops (or at least, "as if" it
    > were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
    > be delighted to be proved wrong.


    Not proving you wrong, but let me remark that for a doubly linked list
    the problem becomes trivial in case the linked lists do not contain
    cycles: simply start at the end of both lists. For singly linked lists
    this solution can be mimicked if one allows the use of malloc (or
    constructing a singly linked list that goes the other way). I think
    this solution can be extended to the cycle case with some care and
    administration, but for now I'll just consider the problem somewhat
    underspecified.

    Stijn
     
    , Jan 22, 2008
    #5
  6. <> wrote in message
    > Is there any efficient way of finding the intesection point of two
    > singly linked lists ?
    > I mean to say that, there are two singly linked lists and they meet at
    > some point. I want to find out the addres of the node where the two
    > linked intersect.
    >
    > thanks for any help...
    >

    struct node
    {
    struct node *next;
    void *data;
    int flag;
    }

    Iterate from start one to then end setting all the flags.
    Iterate from start two. When you find a set flag, that's your merge point.

    Horrid hack.
    For some reason we cannot carry a flag about. So reverse the bits of the
    next pointer. Almost always you will be able to detect a bit-reversed
    pointer. You keep the start of list one and go through for a second time,
    undoing your bit mangling. Needless to say, the horrid hack is dangerous.

    --
    Free games and programming goodies.
    http://www.personal.leeds.ac.uk/~bgy1mm
     
    Malcolm McLean, Jan 22, 2008
    #6
  7. wrote:

    >> listA: A -- B -- C -- D
    >> \
    >> E -- F -- G
    >> /
    >> listB: H -- I
    >>
    >> You compare A with H, B with I, C with E, D with F, E with G. Now the loop
    >> stops, and q is NULL. You missed the merge point completely.
    >>
    >> I believe this has to be done in two nested loops (or at least, "as if" it
    >> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
    >> be delighted to be proved wrong.

    >
    > Not proving you wrong, but let me remark that for a doubly linked list
    > the problem becomes trivial


    ....insofar as the above constellation couldn't occur in doubly-linked
    lists. What would the "previous" pointer of E point to?

    robert
     
    Robert Latest, Jan 22, 2008
    #7
  8. Guest

    On Jan 22, 10:23 am, Robert Latest <> wrote:
    > wrote:
    > >> listA: A -- B -- C -- D
    > >> \
    > >> E -- F -- G
    > >> /
    > >> listB: H -- I

    >
    > >> You compare A with H, B with I, C with E, D with F, E with G. Now the loop
    > >> stops, and q is NULL. You missed the merge point completely.

    >
    > >> I believe this has to be done in two nested loops (or at least, "as if" it
    > >> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
    > >> be delighted to be proved wrong.

    >
    > > Not proving you wrong, but let me remark that for a doubly linked list
    > > the problem becomes trivial

    >
    > ...insofar as the above constellation couldn't occur in doubly-linked
    > lists. What would the "previous" pointer of E point to?
    >
    > robert


    Indeed :( time for coffee ..

    Stijn
     
    , Jan 22, 2008
    #8
  9. Guest

    On Jan 22, 3:19 pm, "Malcolm McLean" <> wrote:
    > <> wrote in message
    > >   Is there any efficient way of finding the intesection point of two
    > > singly linked lists ?
    > > I mean to say that, there are two singly linked lists and they meet at
    > > some point. I want to find out the addres of the node where the two
    > > linked intersect.

    >
    > > thanks for any help...

    >
    > struct node
    > {
    >    struct node *next;
    >    void *data;
    >     int flag;
    >
    > }
    >
    > Iterate from start one to then end setting all the flags.
    > Iterate from start two. When you find a set flag, that's your merge point.
    >

    In fact, I also thought of similar kind of solution, but there need
    not be a flag in the node structure. I also thought of using the
    padding bytes inserted in between the members of a structure and put
    some pattern in the padding/unused bytes each time a node is
    traversed. But, there may not be any padding bytes at all.
     
    , Jan 22, 2008
    #9
  10. santosh Guest

    wrote:

    > On Jan 22, 3:19 pm, "Malcolm McLean" <> wrote:
    >> <> wrote in message
    >> > Is there any efficient way of finding the intesection point of two
    >> > singly linked lists ?
    >> > I mean to say that, there are two singly linked lists and they meet
    >> > at some point. I want to find out the addres of the node where the
    >> > two linked intersect.

    >>
    >> > thanks for any help...

    >>
    >> struct node
    >> {
    >> struct node *next;
    >> void *data;
    >> int flag;
    >>
    >> }
    >>
    >> Iterate from start one to then end setting all the flags.
    >> Iterate from start two. When you find a set flag, that's your merge
    >> point.
    >>

    > In fact, I also thought of similar kind of solution, but there need
    > not be a flag in the node structure. I also thought of using the
    > padding bytes inserted in between the members of a structure and put
    > some pattern in the padding/unused bytes each time a node is
    > traversed. But, there may not be any padding bytes at all.


    In addition, padding bytes need not retain their values after a write.
    In fact, I think an attempt to write to them at all invokes undefined
    behaviour.
     
    santosh, Jan 22, 2008
    #10
  11. Guest

    On Jan 22, 4:08 pm, santosh <> wrote:
    > wrote:
    > > On Jan 22, 3:19 pm, "Malcolm McLean" <> wrote:
    > >> <> wrote in message
    > >> > Is there any efficient way of finding the intesection point of two
    > >> > singly linked lists ?
    > >> > I mean to say that, there are two singly linked lists and they meet
    > >> > at some point. I want to find out the addres of the node where the
    > >> > two linked intersect.

    >
    > >> > thanks for any help...

    >
    > >> struct node
    > >> {
    > >> struct node *next;
    > >> void *data;
    > >> int flag;

    >
    > >> }

    >
    > >> Iterate from start one to then end setting all the flags.
    > >> Iterate from start two. When you find a set flag, that's your merge
    > >> point.

    >
    > > In fact, I also thought of similar kind of solution, but there need
    > > not be a flag in the node structure. I also thought of using the
    > > padding bytes inserted in between the members of a structure and put
    > > some pattern in the padding/unused bytes each time a node is
    > > traversed. But, there may not be any padding bytes at all.

    >
    > In addition, padding bytes need not retain their values after a write.
    > In fact, I think an attempt to write to them at all invokes undefined
    > behaviour


    Santosh, Can you please tell me why the padding bytes need not retain
    their values after a write ? Also, you wrote that writing to padding
    bytes may invoke undefined behaviour. Why is it so ? I could not think
    of any reason for that. Can you please tell me the reason behind it.
     
    , Jan 22, 2008
    #11
  12. "Malcolm McLean" <> wrote in message
    news:...
    >
    > <> wrote in message
    > > Is there any efficient way of finding the intesection point of two
    > > singly linked lists ?
    > > I mean to say that, there are two singly linked lists and they meet at
    > > some point. I want to find out the addres of the node where the two
    > > linked intersect.
    > >
    > > thanks for any help...
    > >

    > struct node
    > {
    > struct node *next;
    > void *data;
    > int flag;
    > }
    >
    > Iterate from start one to then end setting all the flags.
    > Iterate from start two. When you find a set flag, that's your merge point.
    >
    > Horrid hack.
    > For some reason we cannot carry a flag about. So reverse the bits of the
    > next pointer. Almost always you will be able to detect a bit-reversed
    > pointer. You keep the start of list one and go through for a second time,
    > undoing your bit mangling. Needless to say, the horrid hack is dangerous.
    >

    I think there may also be a system specific solution depending on where in
    the memory map
    the dynamically allocated storage is.
     
    Ravishankar S, Jan 22, 2008
    #12
  13. <> wrote in message
    On Jan 22, 4:08 pm, santosh <> wrote:
    > wrote:


    >> In addition, padding bytes need not retain their values after a write.
    >> In fact, I think an attempt to write to them at all invokes undefined
    >> behaviour

    >
    >Santosh, Can you please tell me why the padding bytes need not retain
    >their values after a write ? Also, you wrote that writing to padding
    >bytes may invoke undefined behaviour. Why is it so ? I could not think
    >of any reason for that. Can you please tell me the reason behind it.
    >

    He' s wrong on the reading / writing

    memset(x, 0, sizeof(x));

    is correct whether x contains padding bytes or not.
    as is

    memcpy(&y, &x, sizeof(x));

    However padding bytes are designed not to be used by the program. So the
    compiler could notionally use them for a checksum or something. I doubt that
    any compilers actually do this.


    --
    Free games and programming goodies.
    http://www.personal.leeds.ac.uk/~bgy1mm
     
    Malcolm McLean, Jan 22, 2008
    #13
  14. On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
    "" <> wrote:

    >Hi,
    >
    > Is there any efficient way of finding the intesection point of two
    >singly linked lists ?
    >I mean to say that, there are two singly linked lists and they meet at
    >some point. I want to find out the addres of the node where the two
    >linked intersect.
    >
    >thanks for any help...


    Here is a simple approach. Let A and B be the two lists, and let
    count(A) and count(B) be the number of nodes in each list.
    Suppose that count(A) >= count(B). Skip count(A)-count(B)
    elements of list A to get A'. Now A' and B have the same lengths
    so you can compare them element by element until you find the
    merge point. This is an O(length of lists) method.

    There may be an O(length of distances to merge point) algorithm
    but it doesn't occur to me off hand.

    Why is this in comp.lang.c?
     
    Richard Harter, Jan 22, 2008
    #14
  15. Guest

    On Jan 22, 4:45 pm, (Richard Harter) wrote:
    > On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
    >
    > "" <> wrote:
    > >Hi,

    >
    > >   Is there any efficient way of finding the intesection point of two
    > >singly linked lists ?
    > >I mean to say that, there are two singly linked lists and they meet at
    > >some point. I want to find out the addres of the node where the two
    > >linked intersect.

    >
    > >thanks for any help...

    >
    > Here is a simple approach.  Let A and B be the two lists, and let
    > count(A) and count(B) be the number of nodes in each list.
    > Suppose that count(A) >= count(B).  Skip count(A)-count(B)
    > elements of list A to get A'.  Now A' and B have the same lengths
    > so you can compare them element by element until you find the
    > merge point.  This is an O(length of lists) method.
    >
    > There may be an O(length of distances to merge point) algorithm
    > but it doesn't occur to me off hand.
    >
    > Why is this in comp.lang.c?


    great. thanks for the solution.
     
    , Jan 22, 2008
    #15
  16. "Malcolm McLean" <> writes:

    > <> wrote in message
    >> Is there any efficient way of finding the intesection point of two
    >> singly linked lists ?

    <snip>
    > struct node
    > {
    > struct node *next;
    > void *data;
    > int flag;
    > }
    >
    > Iterate from start one to then end setting all the flags.
    > Iterate from start two. When you find a set flag, that's your merge point.
    >
    > Horrid hack.
    > For some reason we cannot carry a flag about. So reverse the bits of
    > the next pointer. Almost always you will be able to detect a
    > bit-reversed pointer.


    The traditional way to find an extra flag bit was always just to use
    one of the bits in the pointer. The most usual being the least
    significant bit since this will often be 0 for link node pointers
    (even on word-addressed machines). You can also easily traverse the
    list even when the bit is "in use" be one mask operation.

    --
    Ben.
     
    Ben Bacarisse, Jan 22, 2008
    #16
  17. Guest

    On Jan 22, 5:01 pm, Ben Bacarisse <> wrote:
    > "Malcolm McLean" <> writes:
    > > <> wrote in message
    > >>   Is there any efficient way of finding the intesection point of two
    > >> singly linked lists ?

    > <snip>
    > > struct node
    > > {
    > >   struct node *next;
    > >   void *data;
    > >    int flag;
    > > }

    >
    > > Iterate from start one to then end setting all the flags.
    > > Iterate from start two. When you find a set flag, that's your merge point.

    >
    > > Horrid hack.
    > > For some reason we cannot carry a flag about. So reverse the bits of
    > > the next pointer. Almost always you will be able to detect a
    > > bit-reversed pointer.

    >
    > The traditional way to find an extra flag bit was always just to use
    > one of the bits in the pointer.  The most usual being the least
    > significant bit since this will often be 0 for link node pointers
    > (even on word-addressed machines).  You can also easily traverse the
    > list even when the bit is "in use" be one mask operation.
    >


    Why do you say that the lsb of the structure pointer will often be 0 ?
    For instance, consider a structure that has three char members.
    struct test {
    char c1;
    char c2;
    char c3;
    };

    Can't a compiler allocate an odd address for this structure. I am
    using gcc over cygwin. I declared an array of 10 such structures and
    printed the address of each of them. I found that some of the
    addresses were odd.
     
    , Jan 22, 2008
    #17
  18. "Richard Harter" <> wrote in message
    > Here is a simple approach. Let A and B be the two lists, and let
    > count(A) and count(B) be the number of nodes in each list.
    > Suppose that count(A) >= count(B). Skip count(A)-count(B)
    > elements of list A to get A'. Now A' and B have the same lengths
    > so you can compare them element by element until you find the
    > merge point. This is an O(length of lists) method.
    >

    That's the answer.

    --
    Free games and programming goodies.
    http://www.personal.leeds.ac.uk/~bgy1mm
     
    Malcolm McLean, Jan 22, 2008
    #18
  19. On Tue, 22 Jan 2008 11:45:16 GMT, (Richard Harter)
    wrote:

    >On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
    >"" <> wrote:
    >
    >>Hi,
    >>
    >> Is there any efficient way of finding the intesection point of two
    >>singly linked lists ?
    >>I mean to say that, there are two singly linked lists and they meet at
    >>some point. I want to find out the addres of the node where the two
    >>linked intersect.
    >>
    >>thanks for any help...

    >
    >Here is a simple approach. Let A and B be the two lists, and let
    >count(A) and count(B) be the number of nodes in each list.
    >Suppose that count(A) >= count(B). Skip count(A)-count(B)
    >elements of list A to get A'. Now A' and B have the same lengths
    >so you can compare them element by element until you find the
    >merge point. This is an O(length of lists) method.
    >
    >There may be an O(length of distances to merge point) algorithm
    >but it doesn't occur to me off hand.


    And here is a method that doesn't depend on knowing the list
    lengths. As before, let A and B be the list lengths. Traverse A
    by one step. Traverse B by three steps, checking to see if it
    there is a match with the last element read from A. Traverse A
    by five more steps, checking for a match with the last element
    read from B. Continue, alternating lists and increasing the
    steps by two each time. When a match is found this way we know
    the difference of distances to the merge point, m. This gives us
    an O(m^2 +D) method where D is the common distance to the merge
    point. This result can probably be improved.

    The second method is a trifle more complicated but doesn't
    require traversing the entire lists.
     
    Richard Harter, Jan 22, 2008
    #19
  20. "" <> writes:

    > On Jan 22, 5:01 pm, Ben Bacarisse <> wrote:

    <snip>
    >> The traditional way to find an extra flag bit was always just to use
    >> one of the bits in the pointer.  The most usual being the least
    >> significant bit since this will often be 0 for link node pointers
    >> (even on word-addressed machines).  You can also easily traverse the
    >> list even when the bit is "in use" be one mask operation.

    >
    > Why do you say that the lsb of the structure pointer will often be 0 ?
    > For instance, consider a structure that has three char members.
    > struct test {
    > char c1;
    > char c2;
    > char c3;
    > };
    >
    > Can't a compiler allocate an odd address for this structure.


    Yes, but I was talking about linked list node pointers. These will
    have at least one pointer in them and, if that is not enough, will
    usually be allocated with malloc.

    Note "usually". We are in system-specific territory here. You can
    probably break this by, for example, having a list node struct with an
    odd size and making a packed array of these (using something like
    __attribute__((packed)) in gcc). A linked list made from this array
    will not all have a 0 LSB.

    --
    Ben.
     
    Ben Bacarisse, Jan 22, 2008
    #20
    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. Chris Ritchey
    Replies:
    7
    Views:
    511
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    501
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    544
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    701
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    805
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page