文科生向文科生讲解递归递归（1）

1.         public static LinkedList<Integer> sum2(LinkedList<Integer> list1, LinkedList<Integer> list2){
   
2. int length1 = list1.size();
   
3. int length2 = list2.size();        
   
4. if(length1!=length2){
   
5. LinkedList<Integer> shortList = length1>length2 ? list2:list1;
   
6. for(int i = Math.abs(length1- length2); i>0; i--){
   
7. shortList.addFirst(0);
   
8. }        
   
9. }        
   
10. LinkedList<Integer> ret = new LinkedList<Integer>();
    
11. int p= sumHelper(ret,list1,list2);
    
12. if(p!=0)
    
13. ret.addFirst(p);
    
14. return ret;
    
15. }
    
16. private static int sumHelper(LinkedList<Integer> result,LinkedList<Integer> list1, LinkedList<Integer> list2){
    
17. if(list1.isEmpty())
    
18. return 0;
    
19. int sum = list1.poll()+list2.poll()+sumHelper(result,list1,list2);
    
20. result.addFirst(sum%10);
    
21. return sum/10;
    
22. }
    

复制代码

已1->4->6 + 2->7->9=4->2->5为例，

①sum=1+2+sumHelper(result,list1,list2);
②sum=4+7+sumHelper(result,list1,list2);
③sum=6+9+sumHelper(result,list1,list2);

之后list1为空，return 0；返回③，sum=15,result变成5，return 进位1，进入②

sum=4+7+1=12，result变成2，return进位1，进入①

sum=1+2+1=4......

文科生转CS，吐出老血啊，共勉吧


想问一下第五行，LinkedList<Integer> shortList = length1>length2 ? list2:list1;如果list1短一些，那么把list1的内容copy给shortlist，之后shortlist空余位置补0，这样会改变list1的值吗？如果list1或者list2不空位置补0，那么sumHelper(LinkedList<Integer> result,LinkedList<Integer> list1, LinkedList<Integer> list2)这个函数没意义啊

敢转就值得佩服了

楼主加油

递归是个入栈出栈的过程，从栈的角度很容易理解的。

想问一下第五行，LinkedList<Integer> shortList = length1>length2 ? list2:list1;如果list1短一些，那么把list1的内容copy给shortlist，之后shortlist空余位置补0，这样会改变list1的值吗？如果list1或者list2不空位置补0，那么sumHelper(LinkedList<Integer> result,LinkedList<Integer> list1, LinkedList<Integer> list2)这个函数没意义啊

楼主加油

lz加油!!!!

readman 发表于 2014-9-20 22:17
lz加油!!!!

大神帮我解答一下问题呗

TonyJang 发表于 2014-9-20 22:18
大神帮我解答一下问题呗

...发个git吧...

readman 发表于 2014-9-20 22:49
...发个git吧...

https://gist.github.com/jyhjuzi/2c61556d5cbe6857a23d