CareerCup

Can we use 2 stacks to store all nodes first and then pop every time to compare the nodes until there is a different, the previous node is the connection point.

that means listA is [NODES SPECIFIC TO A (x in number)]->[COMMON NODES (c)]
and listB is [NODES SPECIFIC TO B (y)]->[COMMON NODES(c)]

if listB is the longer than listA, then
1) find the x+c node from the tail of listB (O(n))
2) go forward one node at a time from head of smaller list (listA) and x+c node from tail of longer list (listB)
3) the point where you reach a common node is the point of intersection

I answered something similar to this. They needed a more efficient solution because here you have to find the lengths of these two linked lists (requiring the full length traversal of both the lists)

If length of linked list is known then traverse the smaller list else select any list for traversal and add the node addresses to a hash table. Next traverse the other list and check presence of each node in the hash table. The first node of the other list which is found in the hash table is the node which is common to both the lists. The complexity of the algo will be O(m+n), where m, n are the lengths of each linked list respectively.

#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *next;
};
int count(struct node **list)
{
struct node *temp;
int c=0;
temp=*list;
while(temp!=NULL)
{
c++;
temp=temp->next;
}
return c;
}
int main()
{
struct node *n1,*n2,*n3,*n4,*n5,*n6,*n7,*temp1,*temp2,*head1,*head2;

int a,b,c,i;



n1=malloc(sizeof(struct node));
n1->data=1;
n1->next=NULL;

n2=malloc(sizeof(struct node));
n2->data=2;
n1->next=n2;
n2->next=NULL;

n3=malloc(sizeof(struct node));
n3->data=3;
n2->next=n3;
n3->next=NULL;

n4=malloc(sizeof(struct node));
n4->data=4;
n3->next=n4;
n4->next=NULL;


n5=malloc(sizeof(struct node));
n5->data=5;
n4->next=n5;
n5->next=NULL;

n6=malloc(sizeof(struct node));
n6->data=6;
n6->next=NULL;

n7=malloc(sizeof(struct node));
n7->data=7;
n6->next=n7;
n7->next=n5;

head1=n1;
head2=n6;

temp1=head1;
temp2=head2;

while(temp1!=NULL)
{
printf(" %d ->",temp1->data);
temp1=temp1->next;
}

printf(" NULL\n\n");

while(temp2!=NULL)
{
printf(" %d ->",temp2->data);
temp2=temp2->next;
}

printf(" NULL\n\n");

a=count(&n1);
b=count(&n6);

printf("\n\nNO. of nodes in the first list is %d and those in the second one is %d\n\n",a,b);

if(temp1==temp2)
if(a>b)
{
c=a-b;
temp1=head1;

for(i=0;i<c;i++)
temp1=temp1->next;
temp2=head2;
while(temp1!=NULL&&temp2!=NULL)
{
i=c;
if(temp1->next==temp2->next)
{

printf("lists intersect after %d node in the smaller list\n",i);
break;
}
else
{
i++;
temp1=temp1->next;
temp2=temp2->next;
}

}
}
else
{
c=b-a;
temp2=head2;
for(i=0;i<c;i++)
temp2=temp2->next;
temp1=head1;
while(temp1!=NULL&&temp2!=NULL)
{
i=c;
if(temp1->next==temp2->next)
{

printf("lists intersect at %d node\n",i);
}
else
{
i++;
temp1=temp1->next;
temp2=temp2->next;
}

}

}
else
{
printf("\nThe lists donot interset\n");

}
return 0;




}




well i thought we need to create the lists and link them statically............this problem will not arise when we do it dynamically...........so this code finds pt. of inersection wrt shorter list

If it is a double linked list we can move from last node to starting node...till we fill nodes which are not equal for both linked lists

we could use a technique called reference counting. Assuming single linked list and we only have pointer to the head of each of them. We go through any one list and assign an integer to each node that keeps track of number of pointers to it.
When we traverse the second time, we would hit a node whose count is already one. So, that is the common node. So we end travelling atmost O(n + m) possibly less as it is given that the list continues after they meet.

well i have to answer that question in my paper.
the condition i have to stand up to are:
m and n is the length of the lists until the common node.
m and n are not given.
the lists are one way lists.
cpu required is O(m + n )

any ideas?

traverse the nodes from last to first, till nodes are same. The last same node will be the answer.

how to do it ??

Ans -> push nodes of each LL in 2 stacks each while traversing the linked list.

while(s1.node == s2.node)
{s1.pop(); s2.pop();}

Logic:
Take first list and while traversing to the end, mark all the nodes as visited. Then start from the other list and as soon as we hit the node where it says that it has already been traversed once, we hit the joining point.
There must be some more interesting solution, this just sounded too simple.

Take a hash map, start from both list A, and B. In each list check if the current node is existed in hash (using address of the node as a key). If a node exists in hash table, so this node is the connection point, otherwise add the node to the hash and go to the next one.