Add Two Numbers 的 javascript 解法

分析

这道题旨在用链表来表示数字，通过链表来计算两个数的和。

需要注意的一点就是当两个数字的和超过 10 之后对进位的处理。

解答

代码以及注释如下：

// 链表节点的构造函数
function ListNode(val){
  this.val = val;
  this.next = null;
}

var addTwoNumbers = function(l1, l2){
  if ( (l1 instanceof ListNode) && (l2 === undefined || l2 === null) ) return l1;
  if ( (l2 instanceof ListNode) && (l1 === undefined || l1 === null) ) return l2;
  if ( !((l1 instanceof ListNode) && (l2 instanceof ListNode)) ) return;

  var flag = 0,     // 是否有进一位的标识
      v1,           // 链表 l1 在当前位的值
      v2,           // 链表 l2 在当前位的值
      sum,          // 两个链表在某一位上的和
      list = new ListNode(),  // 指向最终结果链表
      p = list;     // 指向链表节点

  // 链表 l1 和 l2 中只要仍有一个链表没有遍历完成，循环就不会结束
  while( l1 || l2 ){
    v1 = l1 && l1.val;
    v2 = l2 && l2.val;

    // 链表 l1 和 l2 中可能有某一方已经遍历结束了，则设该链表在该位置的值为 0
    sum = v1 ? v1 : 0;
    sum += v2 ? v2 : 0;

    // 比当前位低一位的两个数字相加之后有进位，当前位的和需要 +1
    if ( flag ) sum += flag;

    // 若有进位，需要调整 sum 的值
    if ( sum >= 10 ) {
      sum = sum - 10;
      flag = 1;
    } else {
      flag = 0;
    }

    // 若是链表 list 的第一个节点，给链表 list 的第一个节点赋值
    if ( list.val === undefined ) {
      list.val = sum;
    } else {
      // 新建一个节点并插入到链表 list 尾部
      p.next = new ListNode(sum);
      p = p.next;
    }

    // 遍历
    l1 = l1 && l1.next;
    l2 = l2 && l2.next;
  }

  // 两个链表都遍历完了，这时发现最高位有进位，则需要再在最高位之后补上一位
  if ( flag === 1 ) p.next = new ListNode(1);

  // 返回链表
  return list;
}