Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Last active October 13, 2023 19:47
  • Star 12 You must be signed in to star a gist
  • Fork 9 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mycodeschool/5bc53cb87905f95e12b3 to your computer and use it in GitHub Desktop.
#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;
}
@stymsingh
Copy link

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.

@yung-coder
Copy link

#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 node
findmergepoint(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->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 node
c=findmergepoint(head,head1);
printf("%d",c->data);
}
//correct one in c language

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment