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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.