How to find merge point of two linked lists

Let us take two linked lists which at some point merge as one list. Our goal is to find the point where the given two linked lists merging.

two lists merging at node 7.

The most optimized solution for this problem is to find the maximum length list and jump each node until both lists length becomes the same. Below is the code that does move nodes in a bigger list.

    int list1Size = listSize(list1);
    int list2Size = listSize(list2);
    int diff = list1Size - list2Size;
    if (diff > 0)
    {
        while (diff > 0)
        {
            list1 = list1->next;
            diff--;
        }
    }
    else
    {
        while (diff < 0)
        {
            list2 = list2->next;
            diff++;
        }
    }

Once processing nodes in both lists are the same, then jump one node at each iteration on both the lists until we reach a common node (which is merging point).

while (list1 != NULL && list2 != NULL &&
           list1 != list2)
    {
        list1 = list1->next;
        list2 = list2->next;
    }

The above code checks the common merging node. Let’s see the complete code for this problem.

#include <iostream>

using namespace std;

// List node structure
struct Node
{
    int data;
    struct Node *next;
};

// Helper function to create new node.
struct Node *createNode(int data)
{
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Helper function to get the size of list.
int listSize(struct Node *head)
{
    int count = 0;
    struct Node *curr = head;
    while (curr != NULL)
    {
        curr = curr->next;
        count++;
    }
    return count;
}

int main()
{
    struct Node *common = createNode(7);
    common->next = createNode(5);
    common->next->next = createNode(3);

    struct Node *list1 = createNode(15);
    list1->next = createNode(11);
    list1->next->next = common;

    struct Node *list2 = createNode(9);
    list2->next = common;

    int list1Size = listSize(list1);
    int list2Size = listSize(list2);
    int diff = list1Size - list2Size;
    if (diff > 0)
    {
        while (diff > 0)
        {
            list1 = list1->next;
            diff--;
        }
    }
    else
    {
        while (diff < 0)
        {
            list2 = list2->next;
            diff++;
        }
    }
    while (list1 != NULL && list2 != NULL &&
           list1 != list2)
    {
        list1 = list1->next;
        list2 = list2->next;
    }
    if (list1 == NULL || list2 == NULL)
    {
        cout << "Lists not merging" << endl;
        return -1;
    }
    cout << "Merge node: " << list1->data << endl;
    return 0;
}
// Output
$./a.out
Merge node: 7

The complexity of this solution is O(n). This how we find merging nodes of two given linked lists. If you know any better approach please let our readers know by commenting here below.

Advertisements