FindMergePointOfLinkedList.cpp

#include<iostream>
#include<cstdlib>
#include<set>
using namespace std;

struct Node {
    int data;
    struct Node *next;
};
int length(struct Node *head) {
    int len = 0;
    while(head != NULL) {
        len++;
        head = head->next;
    }
    return len;
}
//finds the intersection of the given linked lists version1
//Brute force approach
struct Node* findMergePoint1(struct Node *A, struct Node *B) {
    int m = length(A);  //O(m)
    int n = length(B);  //O(n)
    struct Node* head2 = B;
    for(int i=0;i<m;i++) {
        B = head2;
        for(int j=0;j<n;j++) {
            if(A == B) {
                return A;
            }
            B = B->next;
        }
        A = A->next;
    }
    return NULL;
}
//finds the intersection of the given linked lists version2
//Using memory in brute force
struct Node* findMergePoint2(struct Node *A, struct Node *B) {
    int m = length(A);  //O(m)
    int n = length(B);  //O(n)
    set<Node *> addresses;  //requires #include<set>
    for(int i=0;i<n;i++) {  //O(n log n)
        addresses.insert(B);    //O(log n)
        B = B->next;
    }
    for(int i=0;i<m;i++) {  //O(m log n)
        if(addresses.find(A) != addresses.end()) {  //O(log n)
            return A;
        }
        A = A->next;
    }
    return NULL;
    //Overall Complexity -> O(m log n + n log n)
}
//finds the intersection of the given linked lists version3
//The best approach to solve
struct Node* findMergePoint3(struct Node *A, struct Node *B) {
    int m = length(A);
    int n = length(B);
    int d = n - m;
    if(m > n) {
        struct Node* temp = A;
        A = B;
        B = temp;
        d = m - n;
    }
    int i;
    for(i=0;i<d;i++) {
        B = B->next;
    }
    while(A != NULL && B != NULL) {
        if(A == B) {
            return A;
        }
        A = A->next;
        B = B->next;
    }
    return NULL;
}
int main()
{
    // Code to test the logic, creating 7 nodes and linking them together as
    // two linked list merging at a point. 
    struct Node *head1 = NULL, *head2 = NULL;
    struct Node *temp[7];
    for(int i=0;i<7;i++) {
        temp[i] = (Node *)malloc(sizeof(Node));
    }
    temp[0]->data = 4;
    temp[0]->next = temp[1];
    temp[1]->data = 6;
    temp[1]->next = temp[2];
    temp[2]->data = 7;
    temp[2]->next = temp[3];
    temp[3]->data = 1;
    temp[3]->next = NULL;
    temp[4]->data = 9;
    temp[4]->next = temp[5];
    temp[5]->data = 3;
    temp[5]->next = temp[6];
    temp[6]->data = 5;
    temp[6]->next = temp[2];

    head1 = temp[0];
    head2 = temp[4];
    struct Node *C = findMergePoint3(head1, head2); // You can change method name to call function with other approaches. 
    cout<<C->data;
    return 0;
}

A==B gave me an error, I think the data part need to be compared

no here we are not comparing the value but here we are comparing the addresses of the two nodes.
That's why we use A==B and not A->data == B->data.

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node next;
};
void linkedListTraversal(struct node ptr)
{
while (ptr != NULL)
{
printf("Element: %d\n", ptr->data);
ptr = ptr->next;
}
}
int length(struct node ptr)
{
int count=0;
while (ptr != NULL)
{
count++;
ptr = ptr->next;
}
return count;
}
struct nodefindmergepoint(struct nodeA,struct nodeB)
{
int m = length(A);
int n = length(B);
int d = n - m;
if(m > n) {
struct node* temp = A;
A = B;
B = temp;
d = m - n;
}
int i;
for(i=0;i<d;i++) {
B = B->next;
}
while(A != NULL && B != NULL) {
if(A->data == B->data) {
return A;
}
A = A->next;
B = B->next;
}
return NULL;
}
int main()
{
printf("Enter first linked list\n");
struct node *prev,*head,*p;
int n,i;
printf ("number of elements:");
scanf("%d",&n);
head=NULL;
for(i=0;i<n;i++)
{
p=malloc(sizeof(struct node));
scanf("%d",&p->data);
p->next=NULL;
if(head==NULL)
head=p;
else
prev->next=p;
prev=p;
}
printf("Enter second linked list\n");
struct node *prev1,*head1,p1;
int n1,i1;
printf ("number of elements:");
scanf("%d",&n1);
head1=NULL;
for(i=0;i<n1;i++)
{
p1=malloc(sizeof(struct node));
scanf("%d",&p1->data);
p1->next=NULL;
if(head1==NULL)
head1=p1;
else
prev1->next=p1;
prev1=p1;
}
/printf("First\n");
linkedListTraversal(head);
printf("Second\n");
linkedListTraversal(head1);/
struct nodec=findmergepoint(head,head1);
printf("%d",c->data);
}
//correct one in c language