数据结构之两数相加问题

大兄弟 2019年01月05日0   106

题目:

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

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

我一开始的思路就是将这两个链表进行转化:链表->数组->字符串->格式化数字,最后得到可相加的数字后进行加法运算。javascript代码实现:

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    // 函数方式创建链表,没有用到对象来实现
    function createNode(list) {
        var res = new ListNode(list[0]);
        var curr = res;// 其实这里就相当于引用
        for (var k = 1; (list.length - 1) >= k; k++) {
            curr.next = new ListNode(list[k]); // 这里同时也改变了res变量
            curr = curr.next;// 继续下一个子代
        }
        return res;// 返回链表
    }
    // 链表转数组
    function toArr(curr) {
        var arr = [];
        arr.push(curr.val);
        while (curr.next) {
            arr.push(curr.next.val);
            curr = curr.next;
        }
        return arr;
    }
    // 数组倒序
    function descArr(list) {
        var arr = [];
        for (var k = list.length - 1; 0 <= k; k--) {
            arr.push(list[k]);
        }
        return arr;
    }

    var arr1 = descArr(toArr(l1));
    var arr2 = descArr(toArr(l2));
    var sum = parseInt(arr1.join('') || 0) + parseInt(arr2.join('') || 0);
    var arr3 = sum.toString().split('');
    return createNode(descArr(arr3));
};

其实这个方法是可行的,我是使用了编程语言现成加法运算进行解决问题。虽然是可行,但是对于数值过大的数字来说,系统会给予一个科学计数的显示方式来反馈结果,也就是说在上述的转化过程中到了转化数字一步时,会导致得到一个类似于 1e+30 的结果,导致不能再计算下去,所以,面对特别大的数值时,这个方法就变得不可行了。如果能把科学计数问题解决了,这个方案是依然可行的。

官方的解答是类似于人在草稿纸中计算的方法,将一个多位整数分解为一个一位整数进行单独计算,这就是所谓的“逢十进一”俗称“进一”,如上述例子3+4->4+6(进一)->5+2+1得7->0->8,官方java代码解答:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

根据官方给出的思路,撰写javascript版:

var addTwoNumbers = function (l1, l2) {
    // 逢十进一算
    var l = l1, r = l2;
    var res = new ListNode(null);
    var curr = res; // 当前指针
    var carry = 0; // 哑节点 即 进几
    while (l || r || carry) {
        var lnum = 0, rnum=0;
        if(l) lnum = l.val;
        if(r) rnum = r.val;
        var sum = carry + parseInt(lnum) + parseInt(rnum);
        carry = parseInt(sum / 10);// 进一取整数部分
        curr.next = new ListNode(sum % 10); // 取余
        curr = curr.next; // 指针向下
        if(l) l=l.next;
        if(r) r=r.next;
    }
    return res.next;
};