leetcode2-两数相加

jiezi

5 年前

欢迎跟着夏老师一起学习算法，这方面我自己的基础很薄弱，所以解题方法和思路也会讲的很”小白“，不需要什么基础就能看懂。

关注公众号可以进行交流和加入微信群，群内定期有系列文章分享噢！

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

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

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

示例：

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

遍历两个链表把值加起来好之后插入链表，如果有进位的话需要把进位的值保存到后面的节点上，如果遍历完毕之后还剩下需要进位的值，那么需要插入末尾新节点。

遇到链表相关的题目时一定要处理好边界情况，因为有些为空的链表或者只有 1 个节点的链表没有处理的必要，及时返回可以降低算法复杂度。

链表 1 和链表 2 同时为空，直接返回 undefined 即可
链表 1 为空，返回链表 2
链表 2 为空，返回链表 1

// 链表节点定义
function ListNode(val) {
  this.val = val;
  this.next = null;
}

function addTwoNumbers(l1, l2) {if(!l1 && !l2) { // 链表 1 和链表 2 同时为空，无需任何处理
    return;
  }
  if(!l1) { // 链表 1 为空，直接返回链表 2
    return l2;
  }
  if(!l2) { // 链表 2 为空，直接返回链表 1
    return l1;
  }
  
  let carry = 0; // 进位值
  let head = new ListNode(0); // 链表头节点
  let p = head; // 链表移动指针
  
  while(l1 || l2 || carry > 0) { // l1 和 l2 虽然不会同时为空，但是存在 l1 和 l2 长度不一致的情况，这种也需要处理
    let sum = carry; // sum 为本节点的值，需要加上前一个节点的进位值
    if(l1) {
     sum += l1.val; // 把链表 1 当前节点的值加上
     l1 = l1.next; // 移动链表 1 指针
    }
    if(l2) {
      sum += l2.val;
      l2 = l2.next;
    }
    
    if(sum >= 10) { // 两个个位数相加最大值为 18，所以到下一个节点进位的最大值为 1
      carry = 1;
      sum -= 10; // 去掉十位，保留个位为节点最终值
    } else {carry = 0; // 相加之后和小于 10，不需要进位，清除进位数据，否则死循环}
    
    p.next = new ListNode(sum); // 插入新节点
    p = p.next; // 新链表指针后移
  }
  
  return head.next; // 头结点的值不是相加得到的，所以需要后移一个节点返回由两个链表加起来的结果
}

进位的处理搞清楚之后这道题就清楚了。

时间复杂度 O(max(l1.length, l2.length))

循环次数的根据链表 1 和链表 2 中长的那个链表来的，因为要保证两个链表的所有节点都被便利到

空间复杂度 O(max(l1,l2))

最终链表的节点数也是根据链表 1 和链表 2 中长的那个链表来的，因为要保证两个链表的所有节点都被便利到，如果最后有进位的话，结果链表的长度会比链表 1 和链表 2 中长的链表大小 +1。

这道题的难度是中等，但是摸清楚链表的基本操作之后，应该没什么问题就能解决。

leetcode2-两数相加

Question

分析

边界情况

解题方法

结尾