i faced this qn in ********* interview. best soln i could give was:
- traverse each list and derive both the numbers.. something like below node = list->head; i=1; value =0; while (node) { value = (node->data)*i +value; i*=10; node = node->next; } - add both the numbers. u can either return the number or form a new list and return. i gave the code.. and its o(m+n), for lists of size m,n. -Deva On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta <sgup...@gmail.com> wrote: > step 1 is n not m > which makes it O(3n) > > > On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta <sgup...@gmail.com> wrote: > >> its not exponential >> time to find out m = m >> time to create list 3 = m >> time to create list 4 = n-m >> time to come up with proper added list (list 3 modification) = m >> time to merge list 3 and list 4 = n-m >> >> total time = 2n+m >> >> except step 1 all are reversals with approximately same constant and >> constant for step 1 is smaller >> so one can say >> >> O(2n+m) >> >> >> On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia <abhati...@gmail.com>wrote: >> >>> If that is the representation, then the lists have to be reversed. >>> Otherwise the time goes up exponentially. >>> >>> On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase <harishp...@gmail.com> >>> wrote: >>> > Condition: >>> > Can we do it keeping the original lists intact ? ie without reversing >>> it. >>> > I mean , No recursion & no Reversing ... is it possible ? >>> > >>> > @kumar : >>> > 15234 is represented as 1->5->2->3->4 >>> > >>> > On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta <sgup...@gmail.com> >>> wrote: >>> >> >>> >> perhaps you mean, >>> >> reverse each link list O(n+m). >>> >> then sum each node with carryover maintained. >>> >> >>> >> On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia <abhati...@gmail.com> >>> >> wrote: >>> >>> >>> >>> Let us take an example - >>> >>> >>> >>> Num 1 = 123456 >>> >>> Num 2= 1234 >>> >>> Link-1->Link-2->Link-3->Link-4->Link5->Link6 >>> >>> Link-1->Link-2->Link-3->Link-4 >>> >>> >>> >>> Add nodes into linkedlist 1 till either one of the list is not null. >>> >>> Make sure you process the carry in each iteration. >>> >>> >>> >>> >>> >>> --AB >>> >>> >>> >>> >>> >>> On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase <harishp...@gmail.com >>> > >>> >>> wrote: >>> >>> > conditions: >>> >>> > NO extra memory (@ stack or Heap) at all. No recursion. >>> >>> > >>> >>> > Any body has got any hint about how to get this done ? >>> >>> > >>> >>> > >>> >>> > >>> >>> > -- >>> >>> > You received this message because you are subscribed to the Google >>> >>> > Groups >>> >>> > "Algorithm Geeks" group. >>> >>> > To post to this group, send email to algoge...@googlegroups.com. >>> >>> > To unsubscribe from this group, send email to >>> >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>> >>> To unsubscribe from this group, send email to >>> >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>> >> To unsubscribe from this group, send email to >>> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>> > To unsubscribe from this group, send email to >>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.