Merge point of two linked lists

Tags: , , ,

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.
For example, in the figure below, node(5) is the merge point of two linked lists.

merge point of two linked list

How can we identify that two linked list do not merge? Easy, if two linked lists merge at any given node including the last node, the last node should be same. If the last nodes of two linked lists are different, we can safely say that two linked list do not merge.

Merge point of two linked lists

How to find the merge point is the next problem. From the above diagram, notice that all the nodes after merge point are same if two linked list are merged at a certain node. So that part of two linked lists is common to both.
We can use this insight to find the merge point. If lengths of two linked lists are equal, then we can just start a traversal of those lists from heads and they will meet the merge point.

What if the lengths are different? In this case, there is an equal number of nodes in two linked list after the merge point. The difference has to be before the merge point. If we get the difference between the lengths and move the pointer on the longer list head by the difference, we will reach the merge point at the same time when we traverse lists again.

merge point of two linked lists

If length of two linked lists is different, problem reduces to the problem where we need to reach at the end of two lists at the same time. There is a simple solution to that.

Merge point of two linked lists: implementation

#include<stdlib.h>
#include<stdio.h>

typedef struct node{
    int data;
    struct node *next;
} Node;

void print_list(Node * head){
        while(head){
                 printf("%d->" , head->data );
                 head = head->next;
        }

        printf("NULL");
        printf("\n");

}

int merge_point(Node *L1, Node *L2){

        Node * current1 = L1;
        Node * current2  = L2;

        int count_1 = 0;
        int count_2 = 0;
        //If any one list is null, return false
        if(!current1 || !current2 ) return -1;

        //Count number of nodes in list 1;
        while(current1->next){
                count_1++;
                current1 = current1->next;
        }
        // Count number of nodes in list 2
        while(current2->next){
                count_2++;
                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(count_1 - count_2);

        //Move the longer linked list by diff number of nodes
        if(count_1 < count_2){
                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;
}

void push(Node **head, int value){
    if(*head == NULL){
        (*head) = (Node *)malloc(sizeof(Node));
        (*head)->data = value;
        (*head)->next = NULL;
    }
    else{
        Node * newNode= (Node *)malloc(sizeof(Node));
        if(newNode){
            newNode->data = value;
            newNode->next = (*head);
            *head = newNode;
        }
    }
}

void main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
 		push(&L1,3);
 		Node * temp1 = L1;
        push(&L1,4);
        push(&L1,6);
        push(&L1,7);
        push(&L1,8);
        push(&L1,9);
        print_list(L1);
        printf("\n");
        push(&L2,5);
        Node * temp2 = L2;
        push(&L2,7);
        push(&L2,8);
        push(&L2,2);
        push(&L2,1);
        push(&L2,10);
        printf("\n");

        temp2->next = temp1;

        print_list(L2);
        int result1 = merge_point(L1, L2);
        if(result1 != -1){
                printf("\n Merge Point : %d", result1);
        }
        else{
                printf("\n Lists don't merge");
        }
}

The complexity of the algorithm to find merge point of two linked list is O(n), however, we scan the lists multiple times.

Please share if there is something wrong or missing. If you are preparing for an interview and want to have personalized coaching, please signup for a free demo session.