Re: [algogeeks] Re: Intersection of 2 linked lists -
@naveen ,ross and ankit - I know that linked list has only one next pointer and it can point to single point only. Sorry that i didn't explained my example actually it is like LL1 = 1 - 2 - 3 - 4 LL2 = 5 - 7 - 3 - 9 and i mean to said that LL1 and LL2 have node (whose value is 3) are common, so can't we say that LL1 and LL2 are intersecting each other. but by all of your explanations, now i have understand that after node(having digit value 3) in both linked list they must have the same value. LL1 = 1 2 3 4 LL2 = 5 7 3 4 now am i right guys? :) On Thu, Jun 2, 2011 at 10:56 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Arpit : By intersection of the 2 linked lists, we mean that the pointers to a node are common. It does not mean that if 2 nodes have the same data value, they intersect. Also a node can have only 1 next node, not 2. So, in the example provided by u, how can node having data value 3 point to 2 node Thats not possible !! On Thu, Jun 2, 2011 at 10:33 PM, ross jagadish1...@gmail.com wrote: Hi Arpit, I dont think this sort of intersection is possible.. A linked list has only one next pointer and it can point to single node only. In the counter example you gave, the next ptr of node 3 points to two nodes. So, such a case does not arise. On Jun 3, 9:26 am, Arpit Mittal mrmittalro...@gmail.com wrote: L1 L2 1 5 27 3 94 Is this situation not possible? On Thu, Jun 2, 2011 at 10:23 PM, anand karthik anandkarthik@gmail.comwrote: How can that be unless 3 has two next nodes? -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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] Re: Intersection of 2 linked lists -
I have explained what intersection means in my previous post Ankit On Thu, Jun 2, 2011 at 11:07 PM, Arpit Mittal mrmittalro...@gmail.com wrote: @naveen ,ross and ankit - I know that linked list has only one next pointer and it can point to single point only. Sorry that i didn't explained my example actually it is like LL1 = 1 - 2 - 3 - 4 LL2 = 5 - 7 - 3 - 9 and i mean to said that LL1 and LL2 have node (whose value is 3) are common, so can't we say that LL1 and LL2 are intersecting each other. but by all of your explanations, now i have understand that after node(having digit value 3) in both linked list they must have the same value. LL1 = 1 2 3 4 LL2 = 5 7 3 4 now am i right guys? :) On Thu, Jun 2, 2011 at 10:56 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Arpit : By intersection of the 2 linked lists, we mean that the pointers to a node are common. It does not mean that if 2 nodes have the same data value, they intersect. Also a node can have only 1 next node, not 2. So, in the example provided by u, how can node having data value 3 point to 2 node Thats not possible !! On Thu, Jun 2, 2011 at 10:33 PM, ross jagadish1...@gmail.com wrote: Hi Arpit, I dont think this sort of intersection is possible.. A linked list has only one next pointer and it can point to single node only. In the counter example you gave, the next ptr of node 3 points to two nodes. So, such a case does not arise. On Jun 3, 9:26 am, Arpit Mittal mrmittalro...@gmail.com wrote: L1 L2 1 5 2 7 3 9 4 Is this situation not possible? On Thu, Jun 2, 2011 at 10:23 PM, anand karthik anandkarthik@gmail.comwrote: How can that be unless 3 has two next nodes? -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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] Re: Intersection of 2 linked lists -
yeah ok, thanks On Thu, Jun 2, 2011 at 11:13 PM, ankit sambyal ankitsamb...@gmail.comwrote: I have explained what intersection means in my previous post Ankit On Thu, Jun 2, 2011 at 11:07 PM, Arpit Mittal mrmittalro...@gmail.com wrote: @naveen ,ross and ankit - I know that linked list has only one next pointer and it can point to single point only. Sorry that i didn't explained my example actually it is like LL1 = 1 - 2 - 3 - 4 LL2 = 5 - 7 - 3 - 9 and i mean to said that LL1 and LL2 have node (whose value is 3) are common, so can't we say that LL1 and LL2 are intersecting each other. but by all of your explanations, now i have understand that after node(having digit value 3) in both linked list they must have the same value. LL1 = 1 2 3 4 LL2 = 5 7 3 4 now am i right guys? :) On Thu, Jun 2, 2011 at 10:56 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Arpit : By intersection of the 2 linked lists, we mean that the pointers to a node are common. It does not mean that if 2 nodes have the same data value, they intersect. Also a node can have only 1 next node, not 2. So, in the example provided by u, how can node having data value 3 point to 2 node Thats not possible !! On Thu, Jun 2, 2011 at 10:33 PM, ross jagadish1...@gmail.com wrote: Hi Arpit, I dont think this sort of intersection is possible.. A linked list has only one next pointer and it can point to single node only. In the counter example you gave, the next ptr of node 3 points to two nodes. So, such a case does not arise. On Jun 3, 9:26 am, Arpit Mittal mrmittalro...@gmail.com wrote: L1 L2 1 5 27 3 94 Is this situation not possible? On Thu, Jun 2, 2011 at 10:23 PM, anand karthik anandkarthik@gmail.comwrote: How can that be unless 3 has two next nodes? -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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] Re: Intersection of 2 linked lists -
Hi Ankit, Thats was Nice solution ! :) In case we maintain a pointer to the last node in the linked list, then it is O(1) in time right? On Jun 3, 12:00 am, ankit sambyal ankitsamb...@gmail.com wrote: Traverse the 2 linked lists. Check if the node just before NULL is the same in both the linked lists. If it is then there is an intersection(return 1), otherwise not (return 0). The logic is that whenever 2 linked lists intersect, all the nodes starting from the point of intersection to the end of the linked lists are the same. Time Complexity:O(m+n),where m n are the size of the 2 linked lists Space Complexity : O(1) Ankit Sambyal BITS Pilani On Thu, Jun 2, 2011 at 11:54 AM, ross jagadish1...@gmail.com wrote: Given 2 linked lists, determine whether they intersect or not? (question is not find the point of intersection, which i am sure can be done by computing the lengths of both lists (len1 and len2) and traversing the larger list by |len1 - len2| and traversing subsequently until 2 ptrs meet. I am looking for a bettre approach that does not find the intersection pt but whether that the lists intersect or not -- 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 athttp://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] Re: Intersection of 2 linked lists -
Hi ankit, I am just asking my doubt, i am not sure... if linked list say l1 is = 2 3 4 5 linked list l2 is = 1 3 7 9 now we can also say that l1 and l2 intersect at 3. so in this case wouldn't ur soln will fail? or this type of intersection that i am talking about is not possible? On Thu, Jun 2, 2011 at 8:35 PM, ross jagadish1...@gmail.com wrote: Hi Ankit, Thats was Nice solution ! :) In case we maintain a pointer to the last node in the linked list, then it is O(1) in time right? On Jun 3, 12:00 am, ankit sambyal ankitsamb...@gmail.com wrote: Traverse the 2 linked lists. Check if the node just before NULL is the same in both the linked lists. If it is then there is an intersection(return 1), otherwise not (return 0). The logic is that whenever 2 linked lists intersect, all the nodes starting from the point of intersection to the end of the linked lists are the same. Time Complexity:O(m+n),where m n are the size of the 2 linked lists Space Complexity : O(1) Ankit Sambyal BITS Pilani On Thu, Jun 2, 2011 at 11:54 AM, ross jagadish1...@gmail.com wrote: Given 2 linked lists, determine whether they intersect or not? (question is not find the point of intersection, which i am sure can be done by computing the lengths of both lists (len1 and len2) and traversing the larger list by |len1 - len2| and traversing subsequently until 2 ptrs meet. I am looking for a bettre approach that does not find the intersection pt but whether that the lists intersect or not -- 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 athttp:// 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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] Re: Intersection of 2 linked lists -
How can that be unless 3 has two next nodes? -- 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] Re: Intersection of 2 linked lists -
L1 L2 1 5 27 3 94 Is this situation not possible? On Thu, Jun 2, 2011 at 10:23 PM, anand karthik anandkarthik@gmail.comwrote: How can that be unless 3 has two next nodes? -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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] Re: Intersection of 2 linked lists -
each node in a linked list has one next pointer how can node 3 point to 9 4. On Fri, Jun 3, 2011 at 10:56 AM, Arpit Mittal mrmittalro...@gmail.comwrote: L1 L2 1 5 27 3 94 Is this situation not possible? On Thu, Jun 2, 2011 at 10:23 PM, anand karthik anandkarthik@gmail.com wrote: How can that be unless 3 has two next nodes? -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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. -- Cheers Naveen Kumar -- 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] Re: Intersection of 2 linked lists -
Hi Arpit, I dont think this sort of intersection is possible.. A linked list has only one next pointer and it can point to single node only. In the counter example you gave, the next ptr of node 3 points to two nodes. So, such a case does not arise. On Jun 3, 9:26 am, Arpit Mittal mrmittalro...@gmail.com wrote: L1 L2 1 5 2 7 3 9 4 Is this situation not possible? On Thu, Jun 2, 2011 at 10:23 PM, anand karthik anandkarthik@gmail.comwrote: How can that be unless 3 has two next nodes? -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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] Re: Intersection of 2 linked lists -
@Arpit : By intersection of the 2 linked lists, we mean that the pointers to a node are common. It does not mean that if 2 nodes have the same data value, they intersect. Also a node can have only 1 next node, not 2. So, in the example provided by u, how can node having data value 3 point to 2 node Thats not possible !! On Thu, Jun 2, 2011 at 10:33 PM, ross jagadish1...@gmail.com wrote: Hi Arpit, I dont think this sort of intersection is possible.. A linked list has only one next pointer and it can point to single node only. In the counter example you gave, the next ptr of node 3 points to two nodes. So, such a case does not arise. On Jun 3, 9:26 am, Arpit Mittal mrmittalro...@gmail.com wrote: L1 L2 1 5 2 7 3 9 4 Is this situation not possible? On Thu, Jun 2, 2011 at 10:23 PM, anand karthik anandkarthik@gmail.comwrote: How can that be unless 3 has two next nodes? -- 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. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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.
