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?
Re: Finding the common node of 2 linked lists, without checking the length
Quote:
Originally Posted by
dinari
any ideas?
Is this a problem with a known solution (an exercise) or is it an open research problem?
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.
Re: Finding the common node of 2 linked lists, without checking the length
Quote:
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.
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 :))
Re: Finding the common node of 2 linked lists, without checking the length
Quote:
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.
