两数相加--LeetCode02

两数向加

题目

给出两个 非空 的链表用来表示两个非负的整数。其中它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

• 示例：

none

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

分析

最开始按照题目要求我自己思考的想法是
第一步：先得到数字
第二步：数字相加
第三步：将和转化成ListNode的数据结构

递归数字解法

java

//client方法
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    BigInteger result = new BigInteger(buildNum(l1)).add(new BigInteger(buildNum(l2)));
    return buildNote(result.toString());
}

/**
 * 将链表转化成数字
 */
private static String buildNum(ListNode l1) {
    if (l1.next != null) {
        return buildNum(l1.next) + "" + l1.val;
    } else {
        return String.valueOf(l1.val);
    }
}

/**
* 将数字转化成列表
**/
private static ListNode buildNote(String num) {
    ListNode currentNode;
    if (num.length() > 1) {
        String i = num.substring(0, num.length() - 1);
        currentNode = new ListNode(Integer.valueOf(num.substring(num.length() - 1)));
        currentNode.next = buildNote(i);
    } else {
        currentNode = new ListNode(Integer.valueOf(num));
    }
    return currentNode;
}

• 实验结果

抛出BigInteger不能识别异常，应该是评测程序不能使用相关的引用类。就代表着不能使用数值之和的解法。

移位相加解法

• 代码

java

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //初始化一个新的链表
        ListNode rsNote = new ListNode(0);
        //初始化时将当前节点设置成为rsNode
        ListNode currNode = rsNote;
        ListNode pNode = l1;
        ListNode qNode = l2;
        //表示是否有进位
        int carry = 0;
        while(pNode !=null || qNode != null){
            //当前循环中的node
            int sum = (null!=pNode?pNode.val:0)+(null!=qNode?qNode.val:0)+carry;
            //当前进位
            carry = sum/10;
            //构建出当前node节点
            currNode.next = new ListNode(sum % 10);
            //将下一次使用到的当前节点设置成为此次循环得到的的下一个节点
            currNode = currNode.next;

            //遍历列表中的下一个元素
            pNode = null!=pNode?pNode.next:pNode;
            qNode = null!=qNode?qNode.next:qNode;
        }
        //最后处理最后一个进位数值
        if(carry > 0){
            currNode.next = new ListNode(carry);
        }

        return rsNote.next;
    }

这里使用到的数学原理就只是逢十进位。先设置一个标志位carry，然后计算当前位置的值模除10从而得到当前位置的值。
这里使用了一个技巧，在对这种尾节点进行递增时使用了

java

currNode.next=node;
currNode = currNode.next;

用图来表示

tkiMSU.png

不断的将当前节点顺着链表向下移动，并且给每一个next节点进行赋值。这种方法比递归所占用的空间较小。

总结：

两数向加问题本质上还是要去解决进位问题而不是进行数值计算，这种进位问题应该还可以继续进行优化。