Find merge point of two linked lists

Merge point of two linked lists

Given two linked lists, we need to find out that if two linked list merge, if yes, find merge point of two linked lists.For example:
merge point of two linked lists Answer for above input should be yes and node returned should be 6

Methods to find merge point of two linked lists

First question to be answered is whether or not two linked lists merge?
From above diagram, we can see that when two lists merge, after merge point, all nodes are same. So, that part of two linked list is common for both the lists. If two linked list merge at any given node including last node, the last node should be same. If last node of two linked lists are different, we can safely say that two linked list do not merge.

How to find merge point is second problem? There are couple of ways to find that out.
1. Brute force solution
Use two stacks and follow algorithm below:

1. Put all nodes of linked list 1 on to stack.
2. Put all nodes of linked list 2 on another stack.
3. Pop nodes from two stack simultaneously.
4. When nodes popped are different, node popped prior to them is merge point.

As we can see this takes O(m+n) space. Also linked list are traversed twice.

Second variant can be to use a hash.

1. Scan all nodes of first linked list
   1.a Store nodes into hash Map<Node,Boolean>
2. Now scan second linked list
   2.a Check if current node is present in hash.
   2.b First node which is present will be merge point.

This requires extra O(n) space and traversals of both lists.

Third variant of brute force method is to change linked list node itself. Each node contains a flag ‘visited’.

1. Traverse linked list one and mark nodes as visited.
2. Traverse second list.
    2.a  First node with visited flag as true is merge point

This method does not require extra space however, changes original linked list.

2. Using lengths of merged linked lists
We can leverage the fact that linked list after merge point are same. Consider merge point as end of individual lists.If length of two linked lists is different, problem reduces to the problem where we need to reach at the end of two list at the same time. There is a simple solution to that.
We need to give longer linked list head start so that we reaches end at same time when shorter one reaches, when they are traversed simultaneously. Calculate the difference between length of two linked list and move the longer linked list traversing pointer ahead by difference. Then traverse both linked list together, when they meet that will be the merge point.

Find merge point of two linked lists : implementation

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
        int data;
        struct node *next;
} Node;
 
int findMergePoint(Node *L1, Node *L2){
 
        Node *current1 = L1;
        Node *current2 = L2;
 
        int lengthFirstLinkedList = 0;
        int lengthSecondLinkedList = 0;
 
        //If any one list is null, return false
        if(!current1 || !current2 ) return -1;
 
        //Count number of nodes in list 1;
        while(current1->next){
            lengthFirstLinkedList++;
            current1 = current1->next;
        }
 
        // Count number of nodes in list 2
        while(current2->next){
                lengthSecondLinkedList++;
                current2 = current2->next;
        }
 
        /*If last nodes of both linked list are not same,
        linked list don't merge. */
        if(current1 != current2)
                return -1;
 
        //Calculate the difference in lengths of linked list.
        int diff = abs(lengthFirstLinkedList - lengthSecondLinkedList);
 
        //Move the longer linked list by diff number of nodes
        if(lengthFirstLinkedList < lengthSecondLinkedList){
            Node * temp = L1;
            L1 = L2;
            L2 = temp;
        }
 
        current1 = L1;
        current2 = L2;
 
        while(diff && current1){
                diff--;
                current1 =  current1->next;
        }
 
        // Now move both linked list till they meet at merge point
        while(current1 != current2){
                current1 =  current1->next;
                current2 =  current2->next;
        }
        return current1->data;
}
 
/* Create a node of linked list */
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
 
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node *newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
 
void printList(Node *head){
	printf("\n");
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}
 
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        push(&L1,3);
        push(&L1,4);
        push(&L1,6);
        Node * temp1 = L1;
        push(&L1,7);
        push(&L1,8);
        push(&L1,9);
        printList(L1);
        printf("\n");
 
        push(&L2,5);
        Node *temp2 = L2;
 
        push(&L2,7);
        push(&L2,8);
        push(&L2,2);
        push(&L2,1);
        push(&L2,10);
 
        temp2->next = temp1;
 
        printList(L2);
        int result1 = findMergePoint(L1, L2);

        if(result1 != -1){
                printf("\n Merge Point : %d", result1);
        }
        else{
                printf("\n Lists don't merge");
        }
 
        return 0;
}

Complexity of code to find merge point of two linked lists will be O(N).

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please contact us.