leetcode：两数相加

描述：

题解：

思路一：链表遍历

这道题首先想到的思路跟官方的一致，就是遍历链表，对每个节点进行求和。需要注意的有几点：

1. 两个链表的长度不一定是相等的
2. 相加的过程中会产生进位
3. 链表尾结点产生的进位会导致链表的长度加1

注意到以上几点之后，代码写起来其实是蛮简单的。

ES6

/**
 * 两数相加
 * @param {ListNode} l1 
 * @param {ListNode} l2 
 * @return {ListNode}
 */
export function addTwoNumbers(l1, l2) {
  //声明一个head节点
  const head = new ListNode(null);
  //当前节点
  let curr = head;
  //进位
  let carry = 0;
  //当两个链表都不为空时，每位相加
  while (l1 != null || l2 != null) {
    //链表长度不一致，缺位补0
    let x = l1 != null ? l1.val : 0;
    let y = l2 != null ? l2.val : 0;
    let sum = x + y + carry;
    carry = Number.parseInt(sum / 10);
    curr.next = new ListNode(sum % 10);
    curr = curr.next;
    if (l1 != null) {
      l1 = l1.next;
    }
    if (l2 != null) {
      l2 = l2.next;
    }
  }
  if (carry > 0) {
    curr.next = new ListNode(carry);
  }
  return head.next;
}

时间复杂度：O(n)

Tips:

由于我是用 vscode 来写的，发现一个有趣的问题就是 leetcode 的 javascript 版本默认是做了数组转链表的操作。这个实现起来也比较容易，用对象来模拟一个链表即可。

//声明一个单链表结点
class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

/**
 * 数组转链表
 * @param {Array} arr 
 * @return {ListNode} 
 */
export function array2List(arr) {
  if (arr.length === 0) {
    return null;
  }
  const head = new ListNode(null);
  let i = 0, curr = head;
  for (i; i < arr.length; i++) {
    curr.next = new ListNode(arr[i]);
    curr = curr.next;
  }
  return head.next;
}

上面这段代码有点难理解的就是下面这三句

curr = head
curr.next = new ListNode(arr[i]);
curr = curr.next;

对于这几行代码，如果理解了 js 的引用类型就比较容易看懂，或者画一下堆栈图就更好理解。