Add Two Numbers

[barretlee]

本题难度：★★

两个非空链表，分别代表两个非负整数，链表的每个节点储存着整数的一位，并且是倒序储存的，将这两个数字相加返回新的链表，如：

输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
返回: 7 -> 0 -> 8

提示，这道题需要考虑溢出问题。

参考答案：https://github.com/barretlee/daily-algorithms/blob/master/answers/3.md

[browsnet]

这道题可能太简单了没人过来，我来捧个场，其实链表这个很容易想到做一次单循环相加即可，原理就是小学一年级的加法算式，余1进1，所以时间和空间复杂度都和l1和l2的长度相关，O(max(l1,l2)) 。

var addTwoNumbers = function(l1, l2) {
    var carry = 0,ret = new ListNode(0),l3 = ret;
    while(l1!==null || l2!==null){
        if(l1) {carry += l1.val;l1=l1.next;}
        if(l2) {carry += l2.val;l2=l2.next;}
        l3.next = new ListNode(carry%10)
        l3 = l3.next
        carry = carry>=10?1:0
    }
    if(carry) l3.next = new ListNode(1)
    return ret.next
};

不过我大JS怎么能少了array.reduce呢……

var addTwoNumbers = function(l1, l2) {
    const toArray=l=>l.next?[l.val,...toArray(l.next)]:[l.val];
    const arr=[toArray(l1),toArray(l2)],w=+(arr[0].length<arr[1].length),ret=new ListNode(0);
    const r=arr[w].reduce((r,v,i)=>{
        const v2=arr[+!w][i];
        const x=v2?v2+v+r[1]:v+r[1],l=new ListNode(x%10);
        r[0].next=l;
        return [l,+(x>=10)];
    },[ret,0]);
    r[1]?r[0].next=new ListNode(1):0;
    return ret.next;
};

[pengkobe]

哈哈，是我太傻，居然整了个数组实现，逃~~~已经来不及，先发这吧~

def addLinkedList(a,b):
    addflag = 0 ;
    len_a = len(a);
    len_b = len(b);
    if(len_a == len_b == 0):
        return [];
    ret = [];

    min_len = len_a if len_a < len_b else len_b;
    for i in range(min_len):
        value = a[i] + b[i];
        if addflag == 1:
            value = value + addflag;
        if value >= 10:
            addflag = 1;
            value -= 10;
        else:
            addflag = 0;
        ret.append(value);
    
    temp = a if len_a > len_b else b;
    max_len = len_a if len_a > len_b else len_b;
    for j in range(min_len, max_len):
        if addflag == 1:
             temp[j] =  temp[j] + addflag;
        if temp[j] >= 10:
            addflag = 1;
            temp[j] -= 10;
        else:
            addflag = 0;
            break;
    if addflag == 1:
        temp.append(1);
    ret = ret + temp[min_len:];
        
    return ret;

print (addLinkedList([2,4,3],[5,6,4]))
print (addLinkedList([2,4,3,9,9],[5,6,9]))

[barretlee]

相对数组，链表使用起来要简便很多，在内存中，栈/数组的储存是连续的，如果需要对栈的内部元素做处理（比如删除或者插入），动作会比较大。而链表，可以轻松修改下待处理元素（或者其附近元素）的指针就可以解决问题。

链表实现：https://github.com/barretlee/daily-algorithms/blob/master/ref/linkedlist.js

[barretlee]

使用规范的链表，解法如下：

import LinkedList, {Node} from './linkedlist';

const linkA = new LinkedList(2);
linkA.append(4);
linkA.append(3);

const linkB = new LinkedList(5);
linkB.append(6);
linkB.append(4);

const ret = resolve(linkA, linkB);
console.log(JSON.stringify(ret, null, 2));

function resolve(a, b) {
  const alen = a.length;
  const blen = b.length;
  let count = Math.max(alen, blen);
  let target = a.head, plus = b.head;
  if (alen < blen) {
    target = b.head;
    plus = a.head;
  }
  while(count--) {
    const sum = target.element + plus.element;
    const bits = sum % 10;
    const tens = ~~(sum / 10);
    target.element = bits;
    if (tens && !target.next) {
      target.next = new Node(tens);
    } else if (tens) {
      target.next.element = target.next.element + tens;
    }
    target = target.next;
    plus = plus.next;
  }
  return alen < blen ? b : a;
}

[pengkobe]

@barretlee
while 循环中 plus = plus.next; plus 可能为 undefined，是不是得另做处理？

[barretlee]

function resolve(a, b) {
  const alen = a.length;
  const blen = b.length;
  let count = Math.max(alen, blen);
  let target = a.head, plus = b.head;
  if (alen < blen) {
    target = b.head;
    plus = a.head;
  }
  while(count--) {
-  const sum = target.element + plus.element;
+  const sum = target.element + ( plus && plus.element || 0);
    const bits = sum % 10;
    const tens = ~~(sum / 10);
    target.element = bits;
    if (tens && !target.next) {
      target.next = new Node(tens);
    } else if (tens) {
      target.next.element = target.next.element + tens;
    }
    target = target.next;
-   plus = plus.next;
+   plus = plus && plus.next || null;
  }
  return alen < blen ? b : a;
}

[winar-jin]

第一反应也是用数组实现，感觉解决方案还差好多，先发出来，在去看看答案。👽

  function addTwoNumbers(linkA, linkB) {
      let linkAArr = linkA.split('->');
      let linkBArr = linkB.split('->');
      let totalOfAB = [];
      let otherNum = 0;
      let baselength = linkAArr.length > linkBArr.length ? linkAArr.length : linkBArr.length;
      for (let index = 0; index < baselength; index++) {
        let temp = 0;
        if (linkAArr[index] && linkBArr[index]) {
          temp = parseInt(linkAArr[index]) + parseInt(linkBArr[index]) + otherNum;
        } else if (linkAArr[index]) {
          temp = parseInt(linkAArr[index]) + otherNum;
        } else if (linkBArr[index]) {
          temp = parseInt(linkBArr[index]) + otherNum;
        }
        if (temp < 10) {
          totalOfAB.push(temp);
          otherNum = 0;
        } else {
          totalOfAB.push(parseInt(temp.toString().slice(-1)));
          otherNum = parseInt(temp.toString().slice(0, -1));
        }
      }
      if (otherNum) {
        totalOfAB.push(parseInt(otherNum, 10));
      }
      return totalOfAB.join('->');
    }

[winar-jin]

@barretlee 想知道这种代码的修改时的高亮是怎么实现的？谢谢 ~ （看到您的回复后，我会主动删除这条评论，为了不影响算法的讨论 ~ ）

[barretlee]

@winar-jin 不用删除，没关系，markdown 代码格式选择 diff，第一行第一个字符为 - 便为红色，+ 则为绿色。

- red
- red
+ green
+ green

[YabZhang]

题目要求返回新的链表。

[YabZhang]

from utils import LinkedList, Node

def resolve(alst, blst):
    result = LinkedList()
    shift, first = 0, 1
    anode, bnode = alst.head, blst.head
    while(anode or bnode or shift):
        t_rnode = Node(0)
        if first:
            result.head = t_rnode
            first = 0
        else:
            rnode.next = t_rnode
        rnode = t_rnode
        
        if anode:
           rnode.val += anode.val
           anode = anode.next
        if bnode:
           rnode.val += bnode.val
           bnode = bnode.next

        if shift:
           rnode.val += shift
           shift = 0
        
        if rnode.val // 10:
           shift = rnode.val // 10
           rnode.val %= 10
        else:
           shift = 0
    return result