
April 19th, 2014, 05:57 AM
#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?

April 19th, 2014, 04:53 PM
#2
Re: Finding the common node of 2 linked lists, without checking the length
Originally Posted by dinari
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.

April 20th, 2014, 07:20 AM
#3
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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

April 21st, 2014, 01:39 AM
#4
Re: Finding the common node of 2 linked lists, without checking the length
Originally Posted by 2kaud
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.

April 21st, 2014, 06:22 AM
#5
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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

April 21st, 2014, 08:04 AM
#6
Re: Finding the common node of 2 linked lists, without checking the length
Originally Posted by 2kaud
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

Forum Rules

Click Here to Expand Forum to Full Width
