Instantly share code, notes, and snippets.

Last active October 13, 2023 19:47
Show Gist options
• Save mycodeschool/5bc53cb87905f95e12b3 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #include #include #include 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;inext; } 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 addresses; //requires #include for(int i=0;inext; } for(int i=0;inext; } 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;inext; } 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<data; return 0; }

### CiSr commented Jul 28, 2015

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

### stymsingh commented Aug 27, 2017

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 commented Jan 31, 2022

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node next;
};
{
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()
{
int n,i;
printf ("number of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
p=malloc(sizeof(struct node));
scanf("%d",&p->data);
p->next=NULL;
else
prev->next=p;
prev=p;
}
int n1,i1;
printf ("number of elements:");
scanf("%d",&n1);
for(i=0;i<n1;i++)
{
p1=malloc(sizeof(struct node));
scanf("%d",&p1->data);
p1->next=NULL;
else
prev1->next=p1;
prev1=p1;
}
/printf("First\n");