Find two elements in an array whose sum is x
July 22, 2018
Add numbers given in the form of Linked List
September 5, 2018

Find Merge-Point of two Linked Lists

Given two linked lists that merge at some point as shown below:

Last four nodes are common to both the lists. Given pointers to the header nodes of each list, find the first common node.

Note: If you do not want to read the solution, you can watch the video:

Solution-1: Brute Force
The brute-force solution to this problem is to traverse the first list and for each element in the first list, check if that Node is also present in the second list (Check the address of nodes and not the value because values may be repeating). Return the first node found in the first list that is also present in the second list.
Let us first write a function that searches for a node in the list. This function receives two Node*, the first Node* points to the head of the list and second Node* points to the node that we are searching in this list.

bool searchList(Node* head, Node* data)
{
  while(head != NULL)
  {
    if(head == data)
      return true;
    else
      head = head->next;
  }
  return false;
}

It returns true if Node pointed to by data is present in the list whose head is pointed to by head. Note that we are comparing the address of nodes and not their values. Below function, use this search function to find the first common node:

Node* findPointOfMerge1(Node* h1, Node* h2)
{
  while(h1 != NULL)
    if(searchList(h2, h1))
      return h1;
    else
      h1 = h1->next;
  // LISTS NOT MERGING
  return NULL;
}

In the worst case, this solution takes O(n2) time.
Solution-2: Using the Hash
In the above solution, if we store all the nodes of the second list in a hash-table, then the searching can be constant-time. This will reduce the overall time taken by the solution to O(n). It will, however, take O(n) extra memory.
In Java, we can use a HashMap, below is the C++ code that uses the map class in STL. It first store all the nodes (address of each node) of the second list in the hash:

map<Node*, int> insertInMap(Node* h)
{
  map<Node*, int> hash;
  while(h != NULL)
  {
    hash.insert(pair<Node*, int>(h, 1));
    h = h->next;
  }
  return hash;
}

This function inserts all the node-addresses in the map and the then return that map.
Now the searching logic will search in this map (instead of searching in the linked list):

bool searchInHash(map<Node*, int> hash, Node* data)
{
  map<Node*, int>::iterator it = hash.find(data);
  return (it != hash.end());
}

The main function does not change much,

Node* findPointOfMerge2(Node* h1, Node* h2)
{
  map<Node*, int> hash = insertInMap(h2);
  while(h1 != NULL)
  {
    if(searchInHash(hash, h1))
      return h1;
    else
      h1 = h1->next;
  }
  // LISTS NOT MERGING
  return NULL;
}

This solution takes O(n) time, but also takes O(n) extra memory.
Solution-3: Reversing the list
Another solution can be to reverse the list. Let us assume, that first list has m unique nodes and the second list has n unique nodes and there are p nodes common in both of them:

 If we traverse the first list then we can find the value of (m+p)

Traverse the second list and count the number of nodes, to get the value of (n+p)

Now, reverse the first list. After reversing it, the nodes will look like below:

Now if we traverse the second list, the number of nodes traversed will be shown by the red mark below (which is = m+n+1).

Counting these nodes can give us the value of (m+n+1)

By solving the three equations (1, 2, and 3) we can find the value of variables m, n, and p and then we can find the first common node.
We have already seen how to reverse a linked list in this post.

Node* insertAtHead(Node* h, Node* node)
{
  node->next = h;
  return node;
}
Node* reverseList(Node* h)
{
  Node* newHead = NULL;
  while(h != NULL)
  {
    // REMOVING FROM ORIGINAL LIST
    Node* temp = h;
    h = h->next;
    newHead = insertAtHead(newHead, temp);
  }
  return newHead;
}
int countNodes(Node* h)
{
  int cnt = 0;
  while(h != NULL)
  {
    cnt++;
    h = h->next;
  }
  return cnt;
}
Node* findPointOfMerge3(Node* h1, Node* h2)
{
  int A = countNodes(h1);
  int B = countNodes(h2);
  Node *temp = reverseList(h1);
  int C = countNodes(h2);
  int n = (C+B-A-1)/2;
  reverseList(temp);
  for(int i=0; h2!=NULL &&  i<n; i++) h2 = h2->next;
  return h2;
}

We have written a separate function to count the number of nodes in a linked list, because we are using this functionality multiple times.
It reverses the first list again to restore the original structure. Note that this solution will fail if the two nodes are not merging.
This solution takes O(n) time and constant extra memory. (Reversing a list takes O(n) time).
Solution-4: Best solution
We have saved the best solution for the end. Actually, we do not need to reverse the list at all. If there are more node in the first list, then move h1 forward so that, number of nodes in the first list is equal to number of node in the second list:

Now, the number of nodes in both the lists are equal. Traverse the two lists simultaneously till we reach the same node. This node is the common node.

Node* findPointOfMerge4(Node* h1, Node* h2)
{
  // COUNT THE NODES IN TWO LISTS
  int cnt1 = countNodes(h1);
  int cnt2 = countNodes(h2);
  if(cnt1>cnt2)
  {
    // IF FIRST LIST HAS MORE NODES
    for(int i=0; i<cnt1-cnt2; i++) h1 = h1->next;
  }
  else
  {
    // IF SECOND LIST HAS MORE NODES
    for(int i=0; i<cnt2-cnt1; i++) h2 = h2->next;
  }
  while(h1 != h2)
  {
    h1 = h1->next;
    h2 = h2->next;
  }
  return h1;
}

We are using the function countNodes in this solution also.
It uses O(n) time and constant memory. Asymptotically, the time and extra memory taken in this solution is same as the time and space taken in the previous solution, but, this is probably the most optimal solution.
Complete code

#include <iostream>
#include <map>
using namespace std;
struct Node
{
  char data;
  Node* next;
  // CONSTRUCTOR
  Node(char x): data(x), next(NULL){}
};
Node* createFirstList()
{
  Node* h = new Node('A');
  h->next = new Node('B');
  h->next->next = new Node('C');
  h->next->next->next = new Node('M');
  h->next->next->next->next = new Node('N');
  h->next->next->next->next->next = new Node('O');
  h->next->next->next->next->next->next = new Node('P');
  return h;
}
Node* createSecondList(Node* firstListNode)
{
  Node* h = new Node('R');
  h->next = new Node('S');
  h->next->next = firstListNode; // MERGING WITH FIRST LIST
  return h;
}
void printList(Node* h)
{
  cout<<"\n LIST IS : ";
  while(h != NULL)
  {
    cout<data<<" "; h = h->next;
  }
}
///////// SOLUTION - 1 //////////
bool searchList(Node* head, Node* data)
{
  while(head != NULL)
  {
    if(head == data)
      return true;
    else
      head = head->next;
  }
  return false;
}
Node* findPointOfMerge1(Node* h1, Node* h2)
{
  while(h1 != NULL)
    if(searchList(h2, h1))
      return h1;
    else
      h1 = h1->next;
  // LISTS NOT MERGING
  return NULL;
}
//////// SOLUTION - 2 ///////////
map<Node*, int> insertInMap(Node* h)
{
  map<Node*, int> hash;
  while(h != NULL)
  {
    hash.insert(pair<Node*, int>(h, 1));
    h = h->next;
  }
  return hash;
}
bool searchInHash(map<Node*, int> hash, Node* data)
{
  map<Node*, int>::iterator it = hash.find(data);
  return (it != hash.end());
}
Node* findPointOfMerge2(Node* h1, Node* h2)
{
  map<Node*, int> hash = insertInMap(h2);
  while(h1 != NULL)
  {
    if(searchInHash(hash, h1))
      return h1;
    else
      h1 = h1->next;
  }
  // LISTS NOT MERGING
  return NULL;
}
////////// SOLUTION - 3 //////////////
Node* insertAtHead(Node* h, Node* node)
{
  node->next = h;
  return node;
}
Node* reverseList(Node* h)
{
  Node* newHead = NULL;
  while(h != NULL)
  {
    // REMOVING FROM ORIGINAL LIST
    Node* temp = h;
    h = h->next;
    newHead = insertAtHead(newHead, temp);
  }
  return newHead;
}
int countNodes(Node* h)
{
  int cnt = 0;
  while(h != NULL)
  {
    cnt++;
    h = h->next;
  }
  return cnt;
}
Node* findPointOfMerge3(Node* h1, Node* h2)
{
  int A = countNodes(h1);
  int B = countNodes(h2);
  Node *temp = reverseList(h1);
  int C = countNodes(h2);
  int n = (C+B-A-1)/2;
  reverseList(temp);
  for(int i=0; h2!=NULL &&  i<n; i++) h2 = h2->next;
  return h2;
}
///////// SOLUTION - 4 ///////////
Node* findPointOfMerge4(Node* h1, Node* h2)
{
  int cnt1 = countNodes(h1);
  int cnt2 = countNodes(h2);
  if(cnt1>cnt2)
  {
    for(int i=0; i<cnt1-cnt2; i++) h1 = h1->next;
  }
  else
  {
    for(int i=0; i<cnt2-cnt1; i++) h2 = h2->next;
  }
  while(h1 != h2)
  {
    h1 = h1->next;
    h2 = h2->next;
  }
  return h1;
}
int main()
{
  Node* h1 = createFirstList();
  Node* h2 = createSecondList(h1->next->next->next);
  printList(h1);
  printList(h2);
  Node* temp = findPointOfMerge1(h1, h2);
  if(temp != NULL)
    cout<<"\nLISTS MERGING AT :"<data;
  temp = findPointOfMerge2(h1, h2);
  if(temp != NULL)
    cout<<"\nLISTS MERGING AT :"<data;
  temp = findPointOfMerge3(h1, h2);
  if(temp != NULL)
    cout<<"\nLISTS MERGING AT :"<data;
  temp = findPointOfMerge4(h1, h2);
  if(temp != NULL)
    cout<<"\nLISTS MERGING AT :"<data;
  return 0;
}

Download the code from below link:
https://bitbucket.org/hikrawat/youtube_code/src/master/Interview%20Questions/Linked%20List/Merge%20Point%20Of%20Two%20Lists.cpp

Leave a Reply

Your email address will not be published. Required fields are marked *