NetApp Microsoft Amazon Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
8
of 12 vote

Consider two linked lists L1 and L2
1) Go through L1 and get its length l1
2) Go through L2 and get its length l2
3) Now find the difference d = l1-l2
4) So d is the number of nodes that are extra in longer list.
5) Traverse longer list till 'd' ..keep a pointer at this point
6) Now the length of longer list( That pointer) is equal to length of smaller list from front.
7) Now just traverse the the two list sequentially and compare every Node

Complexity O(n)..

- Yogesh Hande February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

That wont work

what if both have similar lengths looking an 'X' not necessarily intersecting at the middle

- Krishna February 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If both have similar length then you just increment heads of both one by one.
And the approach is , if you have an intersection node then the nodes after the intersection are common to both the lists.
So we just have to find the length of the list before the intersection node.
Please explain why this wont work

- yogeshhan February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

@krishna... think again if it can ever be an X... it can only be a Y.. remember each node can have only one forward link.. once they have a common node, there is only one path to go

- Ankit February 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its is a linked list , so every node has only one next pointer. So this will work. X is not possible since the intersection node will then have 2 next nodes.

- piyushiisc February 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is 1 case where this will not work. What if the 2 linked lists have same elements before the intersection point? In that case this algorithm will not give the correct intersection point. For eg -

1->2->3->3->3->4>5->6
10->11->3->3->3->20
Assume that the 2nd list points to the node with 5 in the 1st list

It will give the intersection point as 3, where as it is 7th number

- codemaniac February 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@codemaniac: you have to compare addresses of pointers not the value in nodes

- Abhi March 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

also the complexity of algo will be O(m^2)......where 'm' is the length of shorter list.

- Abhi March 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No. Complexity is O(n+m+ (n-m) ). Worst case is o(3n.)

- hari@hbiz.in August 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why can't we just traverse thru both the lists and check whether the values are same if same then that is the intersecting point this will iterate until either of the node's next pointer is null or until it find the values are equal.

- Raj August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

These are the following steps:-
1)traverse the first list and reach at the end
2)link the end of first list to the head of second list
3) retain the pointers at the head of both list,also at the end of 1st list
4) problem becomes a->b->c->d->e->f->g->h->e
loop in a linked list and now we have to find the start of loop
5)take two pointers move 1st by one node,second by two
6) when they meet after that take back the 1st to head
7)now move both pointers 1st and second also by one node(from the meeting point)
8)where they meet is the intersection of both list
9)break the link from last of 1st list to head of second

- Anonymous February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

int check( struct node * list1,struct node * list2)
{
int count1 = countLL(list1);
int count2 = countLL(list2);

while(count1> count2)
{
list1 = list1->next;
count1--;
}
while(count2>count1)
{
list2 = list2->next;
count2--;
}

while(list1 ! = list2)
{
list1 = list1->next;
list2 = list2->next;
}
if(list1== null)
{
return 0;/ do not intersect
}
else
return 1; //it intersects


}

- Roshan Mangal January 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A lil bit change... updating code of "Y" scenario with "V" scenario.
1."Y" scenario:
! !
! !
! !
!
!
!
1."V" scenario:
!.....!
!...!
!.!
!
struct node * checkstruct( struct node * list1,struct node * list2)
{
struct node * intersect;
int count1 = countLL(list1);
int count2 = countLL(list2);

while(count1> count2)
{
list1 = list1->next;
count1--;
}
while(count2>count1)
{
list2 = list2->next;
count2--;
}

while(list1 ! = list2)
{
list1 = list1->next;
list2 = list2->next;
}
if(list1=list2)
{
if(list1->next==NULL)
{
printf("it intersects at the last");
}
else
{
printf("it intersects in mid");
}
intersect=list1;
}

else
{

printf("it do not intersect");
intersect=NULL;
}
return intersect;
}

- PKT February 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check your code for two lists,which are not intersecting.
Please tell me,for which case,my code will give wrong result?

- Roshan Mangal February 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

small correction :)

.....
while(list1 ! = list2)
{
list1 = list1->next;
list2 = list2->next;
}
if(list1==list2)//change
{
if(list1->next==NULL)
......

- PKT March 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this wont work for "the revrese of Y case"..

- y so serious? February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this wont work for "the revrese of Y case"..

- y so serious? February 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Another approach :
1. point the last of 1st list to begining of second list.
2. Check if cycle is present (using fast and slow pointer).
3. If cycle is present then these two list merge at some point.
4. to Find the merging point, take two pointers one at the start of 1st list and another at the node where fast and slow pointers meet.
5. increment these two pointers by one each.
6. the node where they meet will be the merging point of two list.

Thanks

- Paras February 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please can you explain with example?

- pan May 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Intersection does not guarantee that they have a cycle!

- Anon November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Algo:
- Find lengths of lists with two given heads. Let us say they are m, n.
- Have two pointers each pointing to given head pointers
- Find abs(m - n), and skip abs(m - n) nodes in the long list
- Compare both pointers. If they match, return. Otherwise, move both pointers by one step. Repeat this step till the lists end

Logic:
- Maximum length of common list < minimum of lengths of linked lists
-- Case - 1: One is a sub-list of the other
-- Case - 2: Both lists are same
- That means big list length - small list length nodes can safely be skipped for comparison

Space Complexity : O(1)
Time Complexity: O(m + n)

Thanks,
Laxmi

- Laxmi Narsimha Rao Oruganti December 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if the address of tail nodes in both linked lists are equal then the linked lists intersect.

to find the intersection..increment a pointer from head of the longer list by L1-L2...where L1 and L2 are lengths of longer and shorter lists. The pointer on L2 starts from its head. Now keep incrementing the pointers of both L1 and L2 till they intersect.

- January 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not necessarily... tht kind of intersection is just one of the 3 possible intersections.. the other 2 are 1) intersection in the shape of X. 2)same head node but diff tail nodes.

- M January 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Normally when we say, two or more link lists intersect, we mean that they share a SAME node at the point of intersection.
If this is what we mean here, then for two lists, shape will look like Y. It can't be of shape X OR /\ (As suggested by M) because one node can't have two different next pointers. With this assumption, v and rosh above are good and saying same thing.
If we mean intersection of list if two nodes a different (at two different memory addresses) but have same value, then we can think of X ot /\ scenarios. But I believe this is not the case here.

- Anurag Singh January 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anu: hey awesome logic.
But i think '/\'is possible in case of common last node. Dont u think..?

- PKT January 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@pkt: anurag is still right because what u implied was actually a 'Y' case with a common last node.

- ramblersm July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nope intersection in de shape of X is not possible coz if it has to occur de middle node should have 2 next pointers n v's sol is rite

- Sathya January 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nope intersection in de shape of X is not possible coz if it has to occur de middle node should have 2 next pointers n v's sol is rite

- Sathya January 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

intersection of two single link-list always be in Y shape, X shape is not possible in any case.

- Gautam Kumar January 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes it is not possible.You can not have a node which is having a single pointer pointing two different nodes.X is not at all possible.

- android lover July 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cudos to M..

- haha January 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void check(struct node *list1, struct node *list2)
{

}

- Anonymous February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void check(struct node *list1, struct node *list2)
{
struct node *temp1, *temp2;
temp1=list1->start;
while(temp1!=NULL
{

}

)
}

- Anonymous February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void check(struct node *list1, struct node *list2)
{
struct node *temp1, *temp2;
temp1=list1->start;
while(temp1!=NULL
{
temp2=list2->start;
while(temp2!=NULL)
{
if(temp1==temp2)
{
printf("Intersection found!"); //at temp1 or temp2
break;
}
temp2=temp2->next;
}
temp1=temp1->next;
}
)
}

- Anonymous February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If two linked lists meet then they should end at the same NULL node (or last node). Traverse both lists and if they both end at the same NULL node (or if the last node is same for both), they meet

- GekkoGordan February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sry didnt read question completely. tulley's solution shud work

- GekkoGordan February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just curious, why won't your solution work?

- gavinashg March 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It does but it doesn't find where they meet ie this solution answers the question partially

- Anonymous March 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Y list problem.
1. Traverse both the list and count nodes.
2. Traverse the bigger one as many nodes as the difference between two.
3. Now traverse both the list simultaneously and keep on checking if both the pointers are pointing to same node.

- Tulley February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we have authority to change the linklist node structure,i'll makrk each visited node of 1st list.

now i'll start traversing on 2nd list & when i'll get marked node then i'll get merging point.

- Rahul Dashore February 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please dont make assumptions while devising a solution.it would be too easy if u can change the node structure. link list means singly link list unless stated otherwise.

- vivekh February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

while(list1 != null && list2 != null )
{
if(list1 == list2)
return true;
else
{
list1=list1->next;
if(list1==list2)
return true;
else
list2=list2->next;
}
}

- pops March 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks Paras for your reply
But I have one question

if the two linked lists meet, the meeting node will have two next pointers pointing to both the linked lists, so while travering in the cycle, how the next pointer will be progressed? I mean towards which linked list?

- Vinita May 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

please can you explain with example?

- pan May 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Assume list 2 to be shorter list, list 1 to be longer one

2) loop x from head:list1 to NULL
loop y from head:list2 to NULL
if ( x == y )
intersection = x;
return;

- shanuapril December 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Finding out if they merge is easy, start with 2 pointers and keep iterating until next pointer is null. If the 2 poiters are now equal, then lists merge. Basically if the last elemet of the 2 lists is the same node, they converge, otherwise not.

now finding out where they merge - can we use a hash and add nodes from first list, then from second list. First node where we hit exception is the one where lists merge, since that will be the first common node.

- amustea December 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not necessarily, as we can have nodes even after the merge point... how do we deal with that?

- Anonymous December 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, but if you insert nodes into the hash in order, then the common node will be the first one to throw that it cannot be inserted into the hash.

- amustea December 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use hashmap then store element addresses, if key is exists then it is merge point.

- SuperK December 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a hashmap to store the addresses of the list elements is working but if the lists are huge this table will be huge.

If memory is the bottleneck and you are willing to pay for time you could do this:
Get the address of the first list item in list-A and search for it in list-B. If found -> bingo. If not get the next item in list-A and repeat. If you cannot find any of the addresses of the items in list-A -> they never merge. (And it does not matter which list you use as list-A and -B)

Actually they always merge in NULL aka the empty list :) but I am not sure all interviewers will love this answer although an empty list is a very nice list and he/she might not like if you ignore this special case on another problem ;)

- Selmeczy, Péter December 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brute Force and O(n2) The solution above is O(n) use that instead.

- RAyden December 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right, I was concentrating so on the memory impact that I missed that point that tails has to be the same length. But usually list do or do not contain their lengths, but still if you have to calculate the length that is better.

- Selmeczy, Péter December 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just compare tails of each list. If they become equal then they merge.

To find out where do they actually meet we can do the reverse traverse till the node is in both list. Thus we get the node where the lists meet.

- coder December 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider two linked lists L1 and L2
1) Go through L1 and get its length l1
2) Go through L2 and get its length l2
3) Now find the difference d = l1-l2
4) So d is the number of nodes that are extra in longer list.
5) Traverse longer list till 'd' ..keep a pointer at this point
6) Now the length of longer list( That pointer) is equal to length of smaller list from front.
7) Now just traverse the the two list sequentially and compare every Node

- yogeshhan February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(l1 + l2)

- Anonymous February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider this example.....
1->2->3->4->5->6->7
2->3->4->5->6->7

here nodes with value 2 and 3 are different nodes in different list...node with value 4 is common node (intersection point) after that 5,6,7 follows.....

In this case your solution will fail....as comparing with node value 2 will result in intersection point but actually it is not.....


The correct solution can be.....

make the next pointer for first list null as we traverse down to the list....
Now traverse other list till null comes...the last node is intersection point.

- Code-Warrior February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider this example.....
1->2->3->4->5->6->7
2->3->4->5->6->7

here nodes with value 2 and 3 are different nodes in different list...node with value 4 is common node (intersection point) after that 5,6,7 follows.....

In this case your solution will fail....as comparing with node value 2 will result in intersection point but actually it is not.....


The correct solution can be.....

make the next pointer for first list null as we traverse down to the list....
Now traverse other list till null comes...the last node is intersection point.

- Code-Warrior February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about if the LLs do not intersect at all?
How can you make that check?

- SS February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

given these two lists:
1->2->3->4->5->6->7 and
a->b->6->c->d, then the intersection point would be 6 right?
If that's the case, then you can find that point with a hash table and the complexity would be O(n+m) (the number of nodes in both lists).

- ep0 February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how can you get 7 and c after 6. You have only one next pointer. so, your example is wrong.

- Anonymous February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can only get y-shaped intersection

- Anonymous February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes exactly only y shaped intersection is possible

- yogeshhan February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Exactly!
A node can point to only one other node!

- r.sachdeva9355 August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// junk.cpp : Defines the entry point for the console application.
//

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


struct node
{
int data;
struct node *next;
};

struct node * insert(struct node *, int );
void insertintersection(struct node *,struct node *, int );
void display(struct node *);
int intersection(struct node *,struct node *);


void main()
{
struct node *head1,*head2,*top;
int x=0,p=0;
head1=NULL;
head2=NULL;

//1st list

head1=insert(head1,10);
head1=insert(head1,20);
head1=insert(head1,30);
head1=insert(head1,40);
head1=insert(head1,50);
head1=insert(head1,60);
head1=insert(head1,70);
head1=insert(head1,80);
head1=insert(head1,90);
head1=insert(head1,100);
printf("1st list is :=>\n");
display(head1);

// 2nd list

head2=insert(head2,1000);
head2=insert(head2,2000);
head2=insert(head2,4000);
head2=insert(head2,5000);
head2=insert(head2,200);
head2=insert(head2,300);
head2=insert(head2,800);
insertintersection(head1,head2,700);
printf("\n2nd list is :=>\n");
display(head2);

p=intersection(head1,head2);
printf("\nintersection point is ==>%d",p);
}

int intersection(struct node *t,struct node *r)
{
struct node *temp1,*temp2;
int count1=0,count2=0,diff=0;

temp1=t;
temp2=r;
while(temp1)
{
temp1=temp1->next;
count1++;
}

while(temp2)
{
temp2=temp2->next;
count2++;
}

diff=count2-count1;

for(;diff>0;diff--)
r=r->next;

while(t->data!=r->data)
{
t=t->next;
r=r->next;
}
return (t->data);
}




struct node * insert(struct node *t,int m)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=m;
temp->next=NULL;

if(t==NULL)
{
t=temp;
}
else
{
r=t;
while(r->next!=NULL)
{
r=r->next;
}
r->next=temp;
}
return t;
}

void insertintersection(struct node *t,struct node*s,int m)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=m;
temp->next=NULL;

while(t->data!=40)
t=t->next;
while(s->next !=NULL)
s=s->next;
s->next=temp;
temp->next=t;

return;

}


void display(struct node *t)
{
struct node *p;
p=t;
while(p)
{
printf("%d->",p->data);
p=p->next;
}
}

- joker February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// junk.cpp : Defines the entry point for the console application.
//

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


struct node
{
int data;
struct node *next;
};

struct node * insert(struct node *, int );
void insertintersection(struct node *,struct node *, int );
void display(struct node *);
int intersection(struct node *,struct node *);


void main()
{
struct node *head1,*head2,*top;
int x=0,p=0;
head1=NULL;
head2=NULL;

//1st list

head1=insert(head1,10);
head1=insert(head1,20);
head1=insert(head1,30);
head1=insert(head1,40);
head1=insert(head1,50);
head1=insert(head1,60);
head1=insert(head1,70);
head1=insert(head1,80);
head1=insert(head1,90);
head1=insert(head1,100);
printf("1st list is :=>\n");
display(head1);

// 2nd list

head2=insert(head2,1000);
head2=insert(head2,2000);
head2=insert(head2,4000);
head2=insert(head2,5000);
head2=insert(head2,200);
head2=insert(head2,300);
head2=insert(head2,800);
insertintersection(head1,head2,700);
printf("\n2nd list is :=>\n");
display(head2);

p=intersection(head1,head2);
printf("\nintersection point is ==>%d",p);
}

int intersection(struct node *t,struct node *r)
{
struct node *temp1,*temp2;
int count1=0,count2=0,diff=0;

temp1=t;
temp2=r;
while(temp1)
{
temp1=temp1->next;
count1++;
}

while(temp2)
{
temp2=temp2->next;
count2++;
}

diff=count2-count1;

for(;diff>0;diff--)
r=r->next;

while(t->data!=r->data)
{
t=t->next;
r=r->next;
}
return (t->data);
}




struct node * insert(struct node *t,int m)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=m;
temp->next=NULL;

if(t==NULL)
{
t=temp;
}
else
{
r=t;
while(r->next!=NULL)
{
r=r->next;
}
r->next=temp;
}
return t;
}

void insertintersection(struct node *t,struct node*s,int m)
{
struct node *temp,*r;

temp=(struct node *)malloc(sizeof(struct node));
temp->data=m;
temp->next=NULL;

while(t->data!=40)
t=t->next;
while(s->next !=NULL)
s=s->next;
s->next=temp;
temp->next=t;

return;

}


void display(struct node *t)
{
struct node *p;
p=t;
while(p)
{
printf("%d->",p->data);
p=p->next;
}
}

- joker February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(Using difference of node counts)
1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

#include<stdio.h>
#include<stdlib.h>
 
/* Link list node */
struct node
{
  int data;
  struct node* next;
};
 
/* Function to get the counts of node in a linked list */
int getCount(struct node* head);
 
/* function to get the intersection point of two linked
   lists head1 and head2 where head1 has d more nodes than
   head2 */
int _getIntesectionNode(int d, struct node* head1, struct node* head2);
 
/* function to get the intersection point of two linked
   lists head1 and head2 */
int getIntesectionNode(struct node* head1, struct node* head2)
{
  int c1 = getCount(head1);
  int c2 = getCount(head2);
  int d;
 
  if(c1 > c2)
  {
    d = c1 - c2;
    return _getIntesectionNode(d, head1, head2);
  }
  else
  {
    d = c2 - c1;
    return _getIntesectionNode(d, head2, head1);
  }
}
 
/* function to get the intersection point of two linked
   lists head1 and head2 where head1 has d more nodes than
   head2 */
int _getIntesectionNode(int d, struct node* head1, struct node* head2)
{
  int i;
  struct node* current1 = head1;
  struct node* current2 = head2;
 
  for(i = 0; i < d; i++)
  {
    if(current1 == NULL)
    {  return -1; }
    current1 = current1->next;
  }
 
  while(current1 !=  NULL && current2 != NULL)
  {
    if(current1 == current2)
      return current1->data;
    current1= current1->next;
    current2= current2->next;
  }
 
  return -1;
}
 
/* Takes head pointer of the linked list and
   returns the count of nodes in the list */
int getCount(struct node* head)
{
  struct node* current = head;
  int count = 0;
 
  while (current != NULL)
  {
    count++;
    current = current->next;
  }
 
  return count;
}

- bkp February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One solution..
1. Go to the end node of common list.
2. Make it point to the head of longer list.Loop will be created
3 Calculate the length of the loop 'x'.
4. Now take two iterator itr1 and itr2. Give head start of x to itr1.
5. Now move both the itrs toward head with same speed.whereever they meet that will be the intersection node.

- Jason February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

exactly as what I thought

- Rocky December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use 2 stacks to store nodes while traversing 2 linkedlists. Then keep popping until you find 2 nodes that are different.

- Larry March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the linklists and then it would be easy to find intersection.

- Shahid March 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

may be a crude/immature or an engineering method

1) L1 = length( list1);
2) L2 = length( list2);
now reverse any of the list [ assume List-1 is reversed ]
3) now starting from head of List-2 find the length = L3

intersection point Ie ( From the end ) = ( L1+L2 - L3 )/2;

intersection point from the begining of list 1 is ( L1- Ie)th node

- Anony April 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a Small correction in the above method

intersection point Ie ( From the end ) = ( L1+L2 - L3-1 )/2;

- Anony April 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about Reverse(L1), Reverse(L2) and then check for a diverging node!
Bad Idea??

- Sri May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

traverse linked list 1
traverse link list 2 simultaneously
until temp1->link==temp2->link;
gives point of intersection

- Anonymous September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;


public class Intersect
{
ArrayList l1 = new ArrayList<Integer>();
ArrayList l2 = new ArrayList<Integer>();

public Intersect()
{
l1.add(1);
l1.add(2);
l1.add(7);
l1.add(4);

l2.add(5);
l2.add(6);
l2.add(7);
l2.add(9);
}
public void findIntersect()
{
int count = 0 ;
for(Object i : l1)
{
if(l2.contains(i))
break;
count++;
}

int l = (l1.size() > l2.size() ? l1.size() : l2.size());

if( count > (l/2) )
System.out.println("Intersection Point is at end");
else if( count < (l/2))
System.out.println("Intersection Point is at start");
else
System.out.println("Intersection Point is at mid");
}
public static void main(String[] args)
{
Intersect i = new Intersect();
i.findIntersect();
}
}

- Pankaj A June 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
import java.util.ArrayList;


public class Intersect
{
ArrayList l1 = new ArrayList<Integer>();
ArrayList l2 = new ArrayList<Integer>();

public Intersect()
{
l1.add(1);
l1.add(2);
l1.add(7);
l1.add(4);

l2.add(5);
l2.add(6);
l2.add(7);
l2.add(9);
}
public void findIntersect()
{
int count = 0 ;
for(Object i : l1)
{
if(l2.contains(i))
break;
count++;
}

int l = (l1.size() > l2.size() ? l1.size() : l2.size());

if( count > (l/2) )
System.out.println("Intersection Point is at end");
else if( count < (l/2))
System.out.println("Intersection Point is at start");
else
System.out.println("Intersection Point is at mid");
}
public static void main(String[] args)
{
Intersect i = new Intersect();
i.findIntersect();
}
}
}}

- Pankaj A June 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

(1)take 2pointers initialize to head of the list
(2)increment both pointer till they reach end of the list and calculate list length l1,l2
(3) calculate absolute difference between l1-l2 ie n=|l1-l2|
(4) calculate nth element from end of the list.

- tomb February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't seem to be right to me...
Did you try with more examples?

- dalef February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I could only think of using a hashtable

- dalef February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

a binary search may be useful.

- Anonymous February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how?

- Ashupriya July 02, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More