Finding the common node of 2 linked lists, without checking the length
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

1. Junior Member
Join Date
Apr 2014
Posts
1

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

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. Banned
Join Date
Aug 2013
Posts
55

## 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.

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.

4. Banned
Join Date
Aug 2013
Posts
55

## 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.

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 )

6. Banned
Join Date
Aug 2013
Posts
55

## 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
•