well, you may reverse them again :-) anyways, assume n > m, since our result is again a new link list with size at most n+1. lets use this storage. We can use this storage to begin with.
take 2 temp pointers and iterate till you reach the end of either one i.e. the smaller one. now say list 2 has length m, say temp pointer p1 is at position n-m in list 1. we have remaining space of n-m, create a new link list 4 which is list 1 reversed from position 1 to n-m. now sum of any 2 nodes is at most 18, start iterating from position n-m+1 (p1) in list 1 and position 1 in list 2. as you proceed start creating a reverse link list with the sums in each node i.e. list 1 = 4->7->8->1->6 list 2 = 2->3->4 list 3 = 10<-4<-10 list 4 = 7->4 now reverse list 3 with the following if no > 9 save a carry over, sum carry over + number. list 3 becomes: 0->5->0 and carry 1. join 3 and 4 taking care of carry over to get (reversing 4 in the process) 4->8->0->5->0 This also assumes you can store integers > 9 in a node which should be fine. 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
