CareerCup

check geeksforgeeks.org/?p=2405

Take two pointers at the start of both the linked lists.Find out the length for both of them. Suppose the length of the linked list are count1 and count2 respectively.
If (count1 > count2) advance the pointer of linked list 1 by count1-count2 nodes.
else advance the pointer of linked list 2 by count2-count1 nodes.
Now start advancing pointers for both the linked lists one by oneand check for the first node when both the poiners are pointing to the same node. This is the node where they merge.
"U 1

In question no where mentioned that after merging at a node both linklist will be same.

for example :

14-15
|
1-2-3-4-5-6-7-8-9
|
11-12-13

@Saurabh your soultion will not work on above problem

@Anonymous: I have assumed a singly linked list which points to a single next node. In the above example , which one are the start nodes of the two linked lists? if they are 15 and 13 my algorithm stands correct. You better think again.

initialise two pointers ,each pointing to the first node of each linked list, increment one of pointers and run the other pointer thru the entire linked list, check for equal addresses pointed by both nodes......

Store the addresses of one of the linked list in the Hash map.
For each element in linked list 2 check if the address exists in the Hash Map.
If it does that is the point of intersection
Time complexity is O(n) and space complexity is also O(n)

Take two start pointer of both link list. Traverse till the end if end node address is common for both link list the these are intersected to each other.

For Findout common node: Find the length of the both link list through traverse.such as m(list1) and n(list2) (n>m). Now take two pointers and set one at starting of list1 and another at (n-m)th node of list2. Now traverse both list and keep comparing the matching node will common one.

One common question that raised in my mind is, if both link lists are singly link list there is only one possibility of intersecting them and that is at the tail node. Otherwise common node has to have two pointers, one to point next node in one list and second to point next node in second list and in singly link list node has only one pointer. So as common node can't really point to two different nodes unless it is last node in both link list and in that case there is no next node.

L1
\ /
\/
[] <---- It is not possible in singly link list
/\
/ \
L2
L1
|
|
|
L2------[] <---- It is possible in singly link list

Other possibility is that both link lists are converging into each other after point of intersection. Means there are more than one common nodes are possible in that case.

L1
\
\ ---- It is possible in singly link list
\
--------[]--------
L2

One common question that raised in my mind is, if both link lists are singly link list there is only one possibility of intersecting them and that is at the tail node. Otherwise common node has to have two pointers, one to point next node in one list and second to point next node in second list and in singly link list node has only one pointer. So as common node can't really point to two different nodes unless it is last node in both link list and in that case there is no next node.

L1
\  /
 \/  
 [] <---- It is not possible in singly link list
 /\
/  \
L2
             L1
             |
             |
             |
    L2------[]  <---- It is possible in singly link list

Other possibility is that both link lists are converging into each other after point of intersection. Means there are more than one common nodes are possible in that case.

      L1
      \
       \    ---- It is possible in singly link list
        \  
--------[]--------
L2

That makes much more sense.....

You could have two lists converging like this:
- - - - - - - - - -
/
/
/
/
List1 has 10 Nodes. List2 has 12 nodes. They converge (intersect) at Node3 of List1 and Node5 of List2.

So first you traverse both lists and get their lengths: List1 = n1. List2 = n2.
n2>n1. Now get the difference: n= n2-n1.
So we know that both lists have n nodes atleast, and the merge happens at one of these nodes.
So for the longer list, list2, advance a pointer to (n2-diff).

Node *cur1 = *head1;
Node *cur2 = *head2;
int pos = 1;
while(pos <= n2-diff)
{
    cur2 = cur2->next;
    pos++;
}

Now walk down both lists together till you find the first nodes that match.

while(cur2 != null && cur1 != null && cur2->data != cur1->data)
{
    cur1 = cur1->next;
    cur2 = cur2->next;
}

if(cur1==null || cur2==null)
   printf("No intersetion");
else
   printf("Intersection at %D", cur1->data);

<pre lang="c" line="1" title="CodeMonkey32827" class="run-this">I have written only function here, driver(main) function is self understood !

/* 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;
}

MB
</pre><pre title="CodeMonkey32827" input="yes">1
2
10
42
11

</pre>

Just wonder why this problem is categorized as "large scale computation"...