CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6
  1. #1
    Join Date
    Apr 2014
    Posts
    1

    Finding the common node of 2 linked lists, without checking the length

    Hello, first of all i have seen the answer about this before, but it is a little bit diffrent.

    i will quote the exact question i have been given:

    You have 2 linked lists, l1 and l2, which merge into 1 list on a certain node, find that node.

    but it must be with O(n+m), when n and m are the length of the 2 lists, Untill the shared node.
    You may use additional O(1) extra memory.

    now i know how to find the common link, when n and m are the total length of the lists, but given the fact that i can only reach to the first common node, i cant find a possible solution, ofc you cant put flags or change the lists.

    any ideas?

  2. #2
    Join Date
    Aug 2013
    Posts
    55

    Re: Finding the common node of 2 linked lists, without checking the length

    Quote Originally Posted by dinari View Post
    any ideas?
    Is this a problem with a known solution (an exercise) or is it an open research problem?
    Last edited by zizz; April 20th, 2014 at 03:17 AM.

  3. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Finding the common node of 2 linked lists, without checking the length

    It's probably an exercise as there seems to be several internet solutions available from a simple google search.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  4. #4
    Join Date
    Aug 2013
    Posts
    55

    Re: Finding the common node of 2 linked lists, without checking the length

    Quote Originally Posted by 2kaud View Post
    It's probably an exercise
    I'm no so sure because of the Ordo measure specifying m and n to be the list lengths up to the intersection point and not the full lengths.

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Finding the common node of 2 linked lists, without checking the length

    As far as I can see, whether m and n are the lengths of the lists up to the intersection point or the full lengths doesn't really matter for at least one of the possible solutions - unless I'm completely misunderstanding something (which is very possible )
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  6. #6
    Join Date
    Aug 2013
    Posts
    55

    Re: Finding the common node of 2 linked lists, without checking the length

    Quote Originally Posted by 2kaud View Post
    As far as I can see, whether m and n are the lengths of the lists up to the intersection point or the full lengths doesn't really matter
    Okay I think I've found it. Very clever indeed.

    It's based on that a common node can be identified that's not necessarily the last node of the lists. Each list has a pointer and they're advanced in turn with an exponentially growing increment. This means one pointer will overtake the other eventually and a common node has been found. The length of the lists up to this node can then be used to find the first common node (the intersection point).

    If the increment doubles in each turn you have a situation that's kind of the inverse of a binary search. Instead of dividing down a certain length by successive halving to 1 the 1 is successively doubled up to the length. And the length in this case is the distance of the most distant list to the intersection point. The overtake will then happen in the next or at most two further doublings.
    Last edited by zizz; April 29th, 2014 at 12:57 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured