Merge Point of two Linked Lists

Problem Statement

This is another interview question which can be linked to the Cycle Detection in Linked List question. In fact this is an extension of the Cycle Detection problem and requires an extra tweaking.

Here is a diagram explaining the the problem of finding the merge point of two linked lists

Merge Point of two Linked Lists

In the above diagram, the head of one linked list is node 1 and the head of another linked list is node 5. The merge point is node 4. We would like to write a program to find node 4 given both the heads.

Approach

There are multiple ways of solving it, here I list three of them:

Brute Force

  • Start from head one and store each node against there hash code in a hash map.
  • Start from head two and check if the hash code already exists in the map.
  • The first node for which the hash code exists is the merge point.

Ah! pretty simple. Brute force actually is pretty simple in this case. Provided you have an algorithm to generate fairly unique hash code as it happens in Java.

Here is a second approach if you are allowed to modify the node structure.

Alternate Solution (Modifying the node structure)

Solution 1

If you are allowed to add one more pointer to the node structure which is a previous pointer, you can successfully assign the previous values to all the nodes except the merge point. And so we know the merge point.

It involves just one traversal of each linked list. Running time would amount to O(M+N) where M and N are the number of nodes in the two linked lists. Space taken would be proportional to M+N. We need space for one pointer in each of the nodes.

Solution 2

Another one, if you are allowed to modify the node structure.

  • You can add a visited flag, initially all set to false.
  • Traverse through one linked list and mark the visited flag to true, if you visit a node.
  • Traverse through the other linked list now and if you encounter a visited flag as true, that’s the merge node.

A Smarter Solution

  • Traverse once through both the linked lists and find the longer one.
  • Connect the tail of the longer list to its head.
  • Now start from the head of the shorter linked list with two pointers as we did in the algorithm to find the cycle.
  • Find the point where both the pointers meet.
  • Reset one of the pointer to the head of the shorter linked list.
  • Now move both the pointers with the same speed (one step at a time).
  • The place where both the pointers meet is the merge point.

Ah! seems complicated isn’t it. But actually its simpler if presented with a visual aid. Here is the modified structure for the above scenario.

Merge Point of two Linked Lists
redefining the problem

In the above case, the fast and the slow pointer starting from node 5 will always meet at 2 and thus the merge point would be node 4.

How do I know that?

This is a simple maths, if we apply our learning from the post which detects a cycle in the linked list. We know the following:

  • The fast and the slow pointer always meet at the same node from where they start.
  • The pointers will meet exactly when the slow pointer completes one circle/cycle.

Let us apply this learning here:

If there was no second linked list, we would have always started at node 4 and both the pointers would have always met at node 4.

Now extending this learning to the current scenario: Lets add just one node to the cycle as shown below:

Merge Point of two Linked Lists
Explaining the relation of cycle to the extended edge

Seeing the image 1 we understand that the blue pointer (Fast one ) moves to node 7 in one step and the green pointer (Slow one)  takes two steps to move to node 7.

This precisely means that they will never meet at node 7 and it proves that, in a scenario without node 6, node 7 cannot possibly be the starting point for both the pointers.

Our job is to find the starting point in the cycle, which surely is not node 7. It means they started somewhere in the past which could be any node (4, 3, 2, 1, 9, 8).

Let us reverse the pointer direction after step 1 which is shown in the Image 2. The step two for the blue pointer takes it to node 3 (it moves two nodes at a time). The step 2 for the green pointer takes it to node 3 (it moves one node at a time).

Both the pointers meet at node 3. This means in a cycle only scenario the starting point was node 3 and every time both the pointers meet at the same node as per our discussion above.

Which concludes our discussion with a generalized result that, in a scenario where the pointers start from an external node and then cycle in a loop, the pointers will always meet at a length K in the reverse from the merge point, where K is the length of the list before the cycle starts.

Hence, our algorithm to find the merge point works seamlessly.

Source Code

Analysis

The running time is an aggregate of all the traversals on the linked lists. We can define it as O(N) where N is the length of the longer linked list.

Space is almost constant O(1), we just use couple of pointers.

  • Azim

    Count the no. of nodes of the both linked lists.
    Say n1, n2 and assume that n1 > n2.

    Find the difference, d = n1 – n2

    Now, move the pointer to d nodes from the head of the longer list.

    node *first = head1;
    node *second = head2;

    while(d>0) {
    first = first -> next;
    d–;
    }

    while(first != second) {

    first = first -> next;

    second = second -> next;

    }

    if(first) {

    printf(“Merge node: %d”, first->data);

    } else {

    printf(“No Merge found.”);

    }