CareerCup

#include "hashtable.h"

node *common(node *head1, node *head2)
{
if (!head1 || !head2)
return null;

node *cur1 = head1;
node *cur2 = head2;

hashtable tbl<int>; //assuming i have a hash table or map

while (cur1)
{
tbl.add(&cur1, 1);
cur1 = cur1->next;
}

while (cur2)
{
int val = 0;
val = tbl.get(&cur2);

if (val == 1) return cur2;
else cur2=cur2->next;
}

return null;
}

I would claim that this has O(max(m,n)) runtime assuming the two lists have m and n elements respectively.

hash table insertion takes O(m) time and second iteration takes O(n) time. Hence, O(m) + O(n) <= O(max(m,n)).

I dont think you need a hashtable. This can be solved using a simple algorithm. Let the 2 lists be listA and listB.

len1 = length_of(listA)
len2 = length_of(listB)

number of common elements = (len1-len2)

now, u can easily find the first common element.

if both head pointers are equal, increment head1 and head2

if they are not, increment the head pointer that was previously not incremented or the pointer that is BEHIND.

steps:

1) create a dummy node

2)start traversing from both the heads simultaneously

3)As you traverse, make the next pointer of each node point to the dummy node.

4) if the next pointer of a node is already pointing to the dummy, then we have found the beginning of the common sequence




NOTE: This spoils the whole linked list though.

Nunbit's solution is the only one I can think of too

giving an example of my solution

INITIAL;
a-b-c-d-
-g-h-i
x-y-z

STEP 1:
Move pointers from 'a' and 'x' to 'b' and 'y'.
Make 'a' and 'x' point to a dummy variable say DUMMY

a-
DUMMY
x-
b-c-d-
g-h-i
y-


STEP 2:
Check if 'b' or 'y' point to DUMMY. Since they don't, follow the same step as before
Move pointers from 'b' and 'y' to 'c' and 'g'.
Make 'b' and 'y' point to DUMMY

a-
b-
- DUMMY
x-
y-


c-d-
- g-h-i



STEP 3:

Check if 'c' or 'g' point to DUMMY. Since they don't, follow the same step as before
Move pointers from 'c' and 'g' to 'd' and 'h'.
Make 'c' and 'g' point to DUMMY

a-
b-
c-
- DUMMY
x-
y-
g-

STEP 4:

Check if 'd' or 'h' point to DUMMY. Since they don't, follow the same step as before
Move pointers from 'd' and 'h' to 'g' and 'i'.
Make 'd' and 'h' point to DUMMY


a-
b-
c-
d-
- DUMMY
x-
y-
g-
h-


STEP 5:
Check if 'g' or 'i' point to DUMMY. 'g' DOES POINT TO DUMMY. SO 'g' is the beginning of the common path!!!!!!!

report 'g'




NOTE: You can do this without using the extra memory by pointing the first list elements to the head of the second list and the second list to the first. That assumes there is no LOOP in the lists.





Hope iam clear!! :)

Cya
Ved.

Start with head1 and head2. Keep comparing the pointers and move ahead both pointers until they are not equal.
When they are equal, that is the first common node.

@sadineni

unfortunately the sizes of the list may not be equal :(

Doesn't the 2nd post solve the question correctly!!!
I dont seem to agree with the rest of the posts.

What if we have duplicates in the list?

well first get the length of each of the link list lets say.
length of the first list = M
-------------second list = N

Diff = M-N

now move M nodes beforehand in the longer list.
then start moving the pointers in both the list when the two
pointers are equal u get the common node.
hope this is clear.

if no memory overhead required then solution by aditya is best otherwise solution posted by anonymous in post 2 is best in time complexity,although Ved is also trying to do the same thing indirectly but the whole list gets disrupted, logically his algo is also correct.

The proposed solution if fine except one case, If the length of the tail is very-very long. In this case you cannot calculate length of lists it will be waste of time. You should come with another, more time consider solution that has time complicity of 0(length of head1 + length of head2).

how wud u maintain the flag node wise... i think u need a hashtable for that... so post 1 is absolutely correct.. both of u r saying the same thing

Hey Ravikant...did u appear for interview at adobe. If yes, pls let us all know the questions.
Thanks in advance

Guys...
If we take difference of lenth of the 2 lists (m-n)
and just skip first (m-n) nodes of the longer list .. as we can b sure they wont b the common part.
On reaching (m-n+1) node of longer list, we are left with 2 lists of size n where last few nodes are common. Then just compare node 1-o-1 till u reach the common portion
this is O(m - length of common portion).

node* FindFirstCommon( node* head1 , node* head2 )
{
if ( !head1 || !head2 )
return NULL ;
int l = length(head1)- length(head2) ;
node* cur1 = head1 ;
node* cur2 = head2 ;
if ( l > 0 )
while ( l > 0 )
{
cur1 = cur1->next ;
--l;
}
else if ( l < 0 )
while ( l < 0 )
{
cur2 = cur2->next ;
l++ ;
}
while ( cur1!= cur2 )
{
cur1->next ;
cur2->next ;
}
// now cur1 and cur2 are pointing to the same element
// print or return the node
cout << cur1->data ;
return cur1 ;
}

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

My approach would be

function FindFirstCommonElement()

len 1 = length of first linked list (traverse it all the way to find it)
len 2 = length of second linked list (traverse it all the way to find it)

diff = len1 - len2 (absolute difference of their lengths)

if (diff >= 0)
{
for i = 1 to diff{
head1 = head1->next;
}
}else{
for i = 1 to |diff|{
head2 = head2->next;
}
}
while (head1->next != head2->next){
head1 = head1->next
head2 = head2->next
}

return (head1->next)

I have another solution, reverse the two lists, use two pointers to traverse both lists, the first k nodes should be of the same value so one pointer should point to a value that is the same as the second pointer, keep moving the pointers until two pointers meet different values.

I think Aditya's solution is good

does this mean that the 2 lists are sorted???

this is simple math problem:
a-b-c-d-e-f-
g-h-i
x-y-z-w-

a to f: x number of nodes
x to z: y number of nodes
g to i: z number of nodes
len(1) = x+z
len(2) = y+z
reverse list from a or x, you will pass x+y nodes.
so you know what is z.
Call me genuis

I don't really understand how some folks to reverse the linked list, with my limited understanding, two linked list could be sth. like this:

a-b-c-d-e-f-
g-h-i
x-y-z-w-

BUT can never be:

-a-b-c-d-e-f-
g-h-i
-x-y-z-w-

HOW can a node has two pointers to next ?

Reversing two lists is good solution.

1. Reverse List A need O(n)
2. reverse List B need O(m)
3. from new heads (old 'tail'), set two pointers to traverse the two lists, when we found they point to diff node, we can know where the diff begins.

Total cost: O(m) + O(n) + "O(0)~O[min(m,n)]"

But I thing I'm still not sure: If we reverse List A first in place, will this operation break the List B since one node can't has two pointers to the next ? could anybody explain what exactly happen when reverse joint Linked List in this case ?

i dont understand why so many ppl are cramming over some simple query...
first 2 soln are cool....and rest crap...
the concept of reversing the two list is complete bulshit...we can'nt have a node pointing to two things at a time...and David pointed it out correctly....guys plz dont waste others valuable time by posting crappy materials ....plz avoid that...if u dont know just watch what others have to say on that instead of disturbing the flow....

hi,guys, the followings are my solution, which takes O(n)(n>m) time. The idea is that we compare the value of element from the end of the lists. Instead of reverse the list, we can use recursion to get the solution. The following are the code, comments are welcome.

int commonlinkedList(list* l1, list* l2) {
static int comVal;
if (l1 == NULL && l2 == NULL)
return comVal;
else {
if (l1 == NULL)
commonlinkedList(l1,l2->next);
else if (l2 == NULL) {
commonlinkedList(l1->next,l2);
}
else {
commonlinkedList(l1->next,l2->next);
}
if (l1->val == l2->val)
comVal = l1->val;
}
return comVal;
}

it is a question which needs to be answered as .....DEPENDS ON THE SIZE OF LIST A AND B
case 1:
if (m-n) is small then traversing both and subtracting the m-n and using 2 pointers method works

case 2:
if one of m/n is very small then other
make a hashmap of smaller list and traverse the bigger and keep checking if the given node is being duplicated...

it is a question which needs to be answered as .....DEPENDS ON THE SIZE OF LIST A AND B
case 1:
if (m-n) is small then traversing both and subtracting the m-n and using 2 pointers method works

case 2:
if one of m/n is very small then other
make a hashmap of smaller list and traverse the bigger and keep checking if the given node is being duplicated...