Interesting Linked-List problem

Artikkeli
08/16/2007

Here's another problem which was given to me by Amit. I had lots of fun solving this :)

Consider two link list as shown above which are joined at some point. The problem statement is as follows

"Given pointers to two single-linked list, find out if they are joined and at which node they are joined. Use constant space to solve this and assume that the nodes cannot be modified. "

From the experience of the previous similar problem I posted let me first explain what is meant by constant space . Constant space means that the algorithm should use constant amount of space and its memory allocation should NOT increase as the length of the list increases. This means ironing out every byte allocation is a NOT a goal (constant space doesn't mean least amount of space). Just ensure that the allocation doesn't increase with the length.

Non-Solution

The above two constrains rules out the two most common brute force algorithms that come to mind

Add another bool/bit field to the nodes and while traversing the list mark the node by setting this field. Check out while traveling in second pass through the other pointer whether any node has this field set which would give the common node. There are some possible optimization over this like traversing the two lists in parallel so that not all the nodes be touched in the first pass.
Create list/hash-tables of the nodes for look up later

My-Solution

I call this my solution because I'm sure there are better solutions to this :). This is O(n) solution.

The pseudo-code

Traverse the first list looking for the last node and compute the list's length (say len1)
Traverse the second list looking for the last node and compute it's length (say len2)
The last nodes of the two list has to be the same if they have joined anywhere in the middle. If not then the lists are not joined and hence return NULL
Find whichever is the longer list (using len1 and len2) and increment the root pointer of that list by abs(len1 - len2). This would ensure that both the pointers are equidistant from joined node.
Make another pass through the list by incrementing both the pointers and at every step ensure if they point to the same node. Since both are equidistant from the joined node (see step 4) this check will succeed and return the joined node.

The C++ code looks something as follows

 // Data-structure for the node
typedef struct Node
{
    Node(int pVal) {
        val = pVal;
        p = NULL;
    }

    int val;
    Node *p;
} *PNODE;

PNODE GetJoinedNode(PNODE LL1, PNODE LL2)
{
    // handle null lists
    if(LL1 == NULL || LL2 == NULL) return NULL;

    PNODE t1 = LL1, t2 = LL2;
    int len1 = 1, len2 = 1;

    // Find first list's length and it's last node
    for(;t1->p != NULL; t1 = t1->p)
        ++len1;

    // find second list's length and it's last node
    for(;t2->p != NULL; t2 = t2->p)
        ++len2;

    // last node not same means no joins in the middle
    if (t1 != t2) return NULL;

    // Advance the longer list by the difference in length so that
    // the pointers are equidistant from the join
    PNODE* t = len1 > len2 ? &LL1 : &LL2;
    AdvanceBy(t, abs(len1 - len2));
    
    // last pass to find the join.
    for(;LL1 != LL2; LL1 = LL1->p, LL2 = LL2->p);

    return LL1;
}

void AdvanceBy(PNODE *pNode, int val) {
    for(int i = 0; i < val; ++i)
        (*pNode) = (*pNode)->p;
}

Comments

Anonymous
August 16, 2007
PingBack from http://www.universityupdate.com/Technology/C-Sharp/4584887.aspx
Anonymous
August 16, 2007
Sigh, by writing this on such a popular site, I think you might have killed this question as a good interview question.
Anonymous
August 21, 2007
That's the same answer I came up with, so it must be right. grin Seriously, I'd be interested in hearing any alternate approaches. As for using this as an interview question - if there are multiple solutions, then this is still an interesting question, for the discussion value.
Anonymous
August 22, 2007
My idea was to walk the link list backwards. Because I thought that when a different number of nodes precede the join (as shown in the picture) you would not compare nodes at the correct position if you walk forwards. (refer to the picture for node numbers) forward iteration would compare: 1-7, 2-8, 3-4, 4-5 not getting any results. backward iteration would compare: 6-6, 5-5, 4-4, 3-8 (and return the last match) or am I wrong...?
Anonymous
August 22, 2007
... I am worng ;-) I see my mistake: its not a double linked list so you can't walk backwards. And I misread the match loop: I missed the pointer magic by the AdvanceBy method...
Anonymous
November 10, 2007
How about the situation that one or both given linked lists may contain a loop?
Anonymous
March 15, 2008
One solution that can tell if they are joined or not (although doesn't tell where they are joined): Make LL1.LastNode.Next point to LL2.FirstNode. Then run the cycle detection code (slow/fast pointer technique) on LL1. If cycle detected, they are joined. If not, they are not.
Anonymous
April 24, 2008
Yes backward traverse is the proper solution i think...
Anonymous
September 14, 2008
The comment has been removed
Anonymous
December 11, 2008
The comment has been removed
Anonymous
November 20, 2009
The number of comparisions can be reduced further. Say Len1 = 12 Len2 = 10 len1 - len2 = 2 Worst case, where only the last nodes join, you will be making 9 comparisions. What can be done is - LL1 and LL2 can be advance by (10/2) which is 5. Check if nodes join. If not, start node-by-node comparisions from there only. Let me know if Im wrong.
Anonymous
March 04, 2010
The comment has been removed
Anonymous
April 02, 2010
I think the first solution is also incorrect. It assumes that after when traversed through len-len2 nodes the indexers on point 1 and point two are equidistant which may not always be the case. Consider the case where The tail of the Longer linked list is merged with the last node of the shorter linked list. Does the solution still hold good>
Anonymous
April 29, 2010
The comment has been removed
Anonymous
April 29, 2010
The comment has been removed
Anonymous
April 30, 2010
The comment has been removed
Anonymous
May 10, 2010
The comment has been removed
Anonymous
May 10, 2010
The comment has been removed
Anonymous
June 09, 2010
abinaba, Sir Can u pls provide links about such problems or more such interesting problems involving linked lists... It would be very helpful!! Thanks in advance!!!
Anonymous
February 14, 2011
This algorithm uses log(n) bits to store the length of the list so it is not constant space but rather log space.

Jaa

Interesting Linked-List problem

Non-Solution

My-Solution

Comments

Lisäresursseja