Add2Nums 问题

两个用单向链表表示的数字加和的问题

题目给出了单向链表的数据结构。然后给出了问题描述：

Add2nums

思路

思路正如上面所说，按位加和，处理进位。

分析

思路简单，但是个人在写代码的时候遇到了几个小问题。

• 加和位数和链表下一个的顺序
  即先建立下一个Node，还是先加和。第一次写代码的时候遇到这样的问题：处理完每一位之后，新建一个Node，到最后，多出来一个空的Node。
  所以这里需要采用，先建立一个 Node，把加和结果写到下一个 Node，进位是上一个 Node 来的进位，这样的计算方式。
• 返回值
  对于链表类问题，返回值必须返回到链表的头。

代码

package day_48;

//  注意链表代表的高低位  1->2->3 : 321
//   所以这里按位来做，处理一下进位就行了

public class Add2Num_2 {
    public ListNode add(ListNode l1,ListNode l2){
        ListNode res = new ListNode(0);
        ListNode copy = res;
        // 上一次来的进位
        int over = 0;
        while (l1!=null || l2!=null){ // 只要有就往后lu
            int a = (l1==null)?0:l1.val;
            int b = (l2==null)?0:l2.val;
            int sum = a+b+over;
            over = sum/10;
            res.next = new ListNode(sum%10);
            res = res.next;
            if(l1!=null) l1 = l1.next;
            if(l2!=null) l2 = l2.next;
            }
        if(over>0) // 考虑最后一次计算是否有进位
            res.next = new ListNode(over);

        // 注意这里最终是要return到链表最开始的地方 所有的链表结构都是这么处理的
        return copy.next;
    }

    public static void main(String args[]){
        Add2Num_2 x = new Add2Num_2();
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);

        ListNode l2 = new ListNode(0);


        System.out.println(x.add(l1,l2));
    }
}

Follow up

这里题目给出了一个 Follow up 问题，说链表不是从低到高位，反过来怎么办。
这样的话肯定就不能按位处理了。
其实第一次我就把题目看错了，看成这种情况了。用了笨办法，先把链表转成 List<>，再转回去。

package day_48;

// 由于看错了链表对应的高低位，所以第一次理解的时候觉得不能用每一位相加进位法
// 这里用了链表转成整数，相加，再转成链表的做法，稍显复杂

import java.util.ArrayList;
import java.util.List;

public class Add2Nums {
    public ListNode add(ListNode l1,ListNode l2){
        ListNode res = new ListNode(0);
        int c = getNum(l1)+getNum(l2);
        int tmp = c;
        int count = 1;
        while (c>=10){
            count *= 10;
            c /= 10;
        }
        while (count>=1){
            int now_digit = tmp/count;
            res.val = now_digit;
            if(count>=10) { // 防止多建一个链表，不然后面总有一个空的链表
                res.next = new ListNode(0);
                res = res.next;
                }
            tmp %= count;
            count /= 10;
        }
        return res;
    }
    public int getNum(ListNode l){  // 把链表转成整数
        int count = 1;
        ListNode tmp = l;
        List<Integer> ref = new ArrayList<Integer>();
        while (tmp.next!=null){
            ref.add(tmp.val);
            count++;
            tmp = tmp.next;
        }
        ref.add(tmp.val); // 把最后一个也加上
        int a = 0;
        for(int i=0;i<ref.size();i++){
            a += ref.get(i)*Math.pow(10.0,count-1);
            count--;
        }
        return a;
    }

    public static void main(String args[]){
        Add2Nums x = new Add2Nums();
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(3);
        System.out.println(x.add(l1,l2));
    }
}