I know the answer (it's 42)

Interesting Linked-List problem

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

1. 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.
2. 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

1. Traverse the first list looking for the last node and compute the list's length (say len1)
2. Traverse the second list looking for the last node and compute it's length (say len2)
3. 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
4. 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.
5. 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;
}