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.
