gravatar

Blog # 37 : Common node in two Linked Lists

Given the heads of two linked lists, find whether they have any common node. If yes, find the common node.
Try to solve it as elegantly as possible.


Solution:

  1. Subtract the length of smaller list from the larger one.
  2. Move a pointer ahead on larger list by the difference of lengths.
  3. Now put a pointer on head of smaller list.
  4. More two pointers together.
  5. The point at which they meet is the point where they short.
Code:
  
Node *getShortedNode(Node *list1, Node *list2){

int d = length(list1) - length(list2);

if(d < 0){
   d = d * (-1);
   Node *tmp = list1;
   list1 = list2;
   list2 = tmp;
}

Node *ptr1 = list1;
for(int i=0; i<d; i++)
{
   ptr1=ptr->next;
}

Node *ptr2 = list2;
while(ptr1 != NULL){
 if(ptr1 == ptr2)
   break;
 ptr1 = ptr1->next;
 ptr2 = ptr2->next;
}
return ptr1;
}

int length(Node *list){
int count = 0;
while(list != NULL){
 list = list->next;
 count++;
}
return count;
}



Save/Share/Bookmark
Category: , , ,
Friday, November 25, 2011 at 11:19 AM
gravatar
anshu rani at February 4, 2012 at 12:38 AM

#include
#include
#include

struct node1 {
int data1;
struct node1 *next;
};
struct node2 {
int data2;
struct node2 *next;
};
int main()
{
struct node1 *temp1,*last1,*first1;
struct node2 *temp2,*last2,*first2;
int i;
int m;
int n;
int count = 0;
printf ("enter the no. of elements for first linked list \n");
scanf ("%d",&m);
printf ("enter the no. of elments for second elements \n");
scanf ("%d",&n);
int num1;
int num2;
printf ("enter the elements for first linked list \n");
first1=NULL;
for (i=0;idata1=num1;
temp1->next=NULL;
first1=temp1;
}
else {
temp1->data1=num1;
temp1->next=NULL;
last1->next=temp1;
}
last1=temp1;
}
printf ("enter the elements for second linked list \n");
first2=NULL;
for (i=0;idata2=num2;
temp2->next=NULL;
first2=temp2;
}
else {
temp2->data2=num2;
temp2->next=NULL;
last2->next=temp2;
}
last2=temp2;
}
struct node1 *s;
struct node2 *t;
for (s=first1;s!=NULL;s=s->next){
for (t=first2;t!=NULL;t=t->next){
if (s->data1==t->data2){
printf ("the common node \n");
printf ("%d\n",t->data2);
count ++;
}
}
}
if(count == 0) {
printf("no common node\n");
}

getch();
return 0;
}

gravatar
anshu rani at February 4, 2012 at 12:45 AM

#include
#include
#include

struct node1 {
int data1;
struct node1 *next;
};
struct node2 {
int data2;
struct node2 *next;
};
int main()
{
struct node1 *temp1,*last1,*first1;
struct node2 *temp2,*last2,*first2;
int i;
int m;
int n;
int count = 0;
printf ("enter the no. of elements for first linked list \n");
scanf ("%d",&m);
printf ("enter the no. of elments for second elements \n");
scanf ("%d",&n);
int num1;
int num2;
printf ("enter the elements for first linked list \n");
first1=NULL;
for (i=0;idata1=num1;
temp1->next=NULL;
first1=temp1;
}
else {
temp1->data1=num1;
temp1->next=NULL;
last1->next=temp1;
}
last1=temp1;
}
printf ("enter the elements for second linked list \n");
first2=NULL;
for (i=0;idata2=num2;
temp2->next=NULL;
first2=temp2;
}
else {
temp2->data2=num2;
temp2->next=NULL;
last2->next=temp2;
}
last2=temp2;
}
struct node1 *s;
struct node2 *t;
for (s=first1;s!=NULL;s=s->next){
for (t=first2;t!=NULL;t=t->next){
if (s->data1==t->data2){
printf ("the common node \n");
printf ("%d\n",t->data2);
count ++;
}
}
}
if(count == 0) {
printf("no common node\n");
}

getch();
return 0;
}