Re: [algogeeks] Finding intersection of 2 linked lists

2012-07-05 Thread Ashish Goel 
struct node* intersection( struct node *pL1, struct node* pL2)
{
   if ((!pL1) || (!pl2)) return NULL;
   struct node * pL3 = NULL;
   struct node* pL3Tail = NULL;
   while(pL1)(pL2) {
if (pL1-data pL2-data) pL1=pL1-next;
else if  (pL1-data  pL2-data) pL2=pL2-next;
else {
   struct node *pNew = (struct node*)malloc(sizeof(struct node));
   if !pNew return NULL; //scary
   pNew-data = pL1-data; pNew-next = NULL;
   if ( !pL3) pL3= pNew;
   else pL3Tail-next = pNew;
   pL3Tail = pNew;
   }
   return pL3;
}




}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652


On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:

 Any efficient algorithm to find intersection of two linked lists.Example:
 Linked List 1)  1 - 2 - 3 - 4 - 5 - 6
 Linked List 2)  3 - 4 - 5

 Intersection 4 - 5 - 6

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Finding intersection of 2 linked lists

2012-07-05 Thread Abhishek Sharma 
@nishant, you wrote until both the distance becomes equal.Which distances
? Could you please elaborate ?

On Thu, Jul 5, 2012 at 12:52 PM, Ashish Goel ashg...@gmail.com wrote:

 struct node* intersection( struct node *pL1, struct node* pL2)
 {
if ((!pL1) || (!pl2)) return NULL;
struct node * pL3 = NULL;
struct node* pL3Tail = NULL;
while(pL1)(pL2) {
 if (pL1-data pL2-data) pL1=pL1-next;
 else if  (pL1-data  pL2-data) pL2=pL2-next;
 else {
struct node *pNew = (struct node*)malloc(sizeof(struct node));
if !pNew return NULL; //scary
pNew-data = pL1-data; pNew-next = NULL;
if ( !pL3) pL3= pNew;
else pL3Tail-next = pNew;
pL3Tail = pNew;
}
return pL3;
 }




 }
 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:

 Any efficient algorithm to find intersection of two linked lists.Example:
 Linked List 1)  1 - 2 - 3 - 4 - 5 - 6
 Linked List 2)  3 - 4 - 5

 Intersection 4 - 5 - 6

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Finding intersection of 2 linked lists

2012-07-05 Thread adarsh kumar 
Hope the following will be of help:
http://www.geeksforgeeks.org/archives/18615

regds.

On Thu, Jul 5, 2012 at 4:32 PM, Abhishek Sharma abhi120...@gmail.comwrote:

 @nishant, you wrote until both the distance becomes equal.Which
 distances ? Could you please elaborate ?


 On Thu, Jul 5, 2012 at 12:52 PM, Ashish Goel ashg...@gmail.com wrote:

 struct node* intersection( struct node *pL1, struct node* pL2)
 {
if ((!pL1) || (!pl2)) return NULL;
struct node * pL3 = NULL;
struct node* pL3Tail = NULL;
while(pL1)(pL2) {
 if (pL1-data pL2-data) pL1=pL1-next;
 else if  (pL1-data  pL2-data) pL2=pL2-next;
 else {
struct node *pNew = (struct node*)malloc(sizeof(struct node));
if !pNew return NULL; //scary
pNew-data = pL1-data; pNew-next = NULL;
if ( !pL3) pL3= pNew;
else pL3Tail-next = pNew;
pL3Tail = pNew;
}
return pL3;
 }




 }
 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:

 Any efficient algorithm to find intersection of two linked
 lists.Example:
 Linked List 1)  1 - 2 - 3 - 4 - 5 - 6
 Linked List 2)  3 - 4 - 5

 Intersection 4 - 5 - 6

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Abhishek Sharma
 Under-Graduate Student,
 PEC University of Technology

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Finding intersection of 2 linked lists

2012-07-05 Thread Nishant Pandey 
both the distance means distance between the two linked list some thing
like this :



struct node *temp1,*temp2;
temp1 = head1;
temp2 = head2;

int l1 = get_dist(head1);
int l2 = get_dist(head2);

int ds = abs(l1-l2);
if( l1  l2 )
{

   for(int i=0;ids;i++)
  {
 if(temp1-next)temp1 = temp1-next;
  }
  // here distance of both the list is equal .
  // now you may traverse like this
   while(temp1  temp2)
   {
   if(temp1 == temp2 )
 // intersection point
  else
   temp1 = temp1-next;
   temp2 = temp2-next;
  // move both one one step a time will come both will meet the
intersection point
  // i hope the point is clear if not let me knw i will send u
the whole code .
   }
}
else
{
   // similary for (l1l2)
}


On Thu, Jul 5, 2012 at 4:32 PM, Abhishek Sharma abhi120...@gmail.comwrote:

 @nishant, you wrote until both the distance becomes equal.Which
 distances ? Could you please elaborate ?


 On Thu, Jul 5, 2012 at 12:52 PM, Ashish Goel ashg...@gmail.com wrote:

 struct node* intersection( struct node *pL1, struct node* pL2)
 {
if ((!pL1) || (!pl2)) return NULL;
struct node * pL3 = NULL;
struct node* pL3Tail = NULL;
while(pL1)(pL2) {
 if (pL1-data pL2-data) pL1=pL1-next;
 else if  (pL1-data  pL2-data) pL2=pL2-next;
 else {
struct node *pNew = (struct node*)malloc(sizeof(struct node));
if !pNew return NULL; //scary
pNew-data = pL1-data; pNew-next = NULL;
if ( !pL3) pL3= pNew;
else pL3Tail-next = pNew;
pL3Tail = pNew;
}
return pL3;
 }




 }
 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652


 On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:

 Any efficient algorithm to find intersection of two linked
 lists.Example:
 Linked List 1)  1 - 2 - 3 - 4 - 5 - 6
 Linked List 2)  3 - 4 - 5

 Intersection 4 - 5 - 6

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Abhishek Sharma
 Under-Graduate Student,
 PEC University of Technology

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Finding intersection of 2 linked lists

2012-07-04 Thread Abhi 
Any efficient algorithm to find intersection of two linked lists.Example: 
Linked List 1)  1 - 2 - 3 - 4 - 5 - 6
Linked List 2)  3 - 4 - 5

Intersection 4 - 5 - 6  

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Finding intersection of 2 linked lists

2012-07-04 Thread Abhishek Sharma 
it was 4 - 5, not 4 - 5 - 6

On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:

 Any efficient algorithm to find intersection of two linked lists.Example:
 Linked List 1)  1 - 2 - 3 - 4 - 5 - 6
 Linked List 2)  3 - 4 - 5

 Intersection 4 - 5 - 6

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Finding intersection of 2 linked lists

2012-07-04 Thread Abhishek Sharma 
3 - 4 - 5, sorry for that silly mistakes

On Wed, Jul 4, 2012 at 10:54 PM, Abhishek Sharma abhi120...@gmail.comwrote:

 it was 4 - 5, not 4 - 5 - 6


 On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:

 Any efficient algorithm to find intersection of two linked lists.Example:
 Linked List 1)  1 - 2 - 3 - 4 - 5 - 6
 Linked List 2)  3 - 4 - 5

 Intersection 4 - 5 - 6

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Abhishek Sharma
 Under-Graduate Student,
 PEC University of Technology




-- 
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Finding intersection of 2 linked lists

2012-07-04 Thread Nishant Pandey 
get the size  of both the linked list say d1,d2 ;
get their diff like df=abs(d1-d2);

now take 2 pointers both poiting to the start of both the linked list .
go to bigger list now move this pointer until both the distance becomes
equal .
at this point we have one pointer from smaller list pointing to the start
of the list and
another pointer in bigger list pointing to node where distance came equal ,
move these 2 pointers until both point to the same node .. and we are done .

On Wed, Jul 4, 2012 at 10:44 PM, Amit Chauhan amitchauhan@gmail.comwrote:

 If both the linked list are ordered one then you can solve this problem in
 linear time and with constant space.



 On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:

 Any efficient algorithm to find intersection of two linked lists.Example:
 Linked List 1)  1 - 2 - 3 - 4 - 5 - 6
 Linked List 2)  3 - 4 - 5

 Intersection 4 - 5 - 6

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.