题目：Add Two Numbers 两数相加

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

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

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

示例：

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

链表类：ListNode

  1. class ListNode {
  2.     int val;
  3.     ListNode next;
  4.     ListNode(int x) { val = x; }
  6.     public static ListNode getLinkedNode(Integer ... nums) {
  7.         LinkedList<Integer> linkedList = new LinkedList();
  8.         Collections.addAll(linkedList, nums);
  9.         return getLinkedNode(linkedList);
  10.     }
  12.     public static ListNode getLinkedNode(List<Integer> nums) {
  13.         Integer num = nums.get(0);
  14.         ListNode listNode = new ListNode(num);
  15.         nums.remove(0);
  16.         if (nums.size() != 0) {
  17.             listNode.next = getLinkedNode(nums);
  18.         }
  19.         return listNode;
  20.     }
  21. }

为了方便，我写了两个工具方法用来构造入参

  1. ListNode a = ListNode.getLinkedNode(new Integer[]{2, 4, 3});
  2. ListNode b = ListNode.getLinkedNode(new Integer[]{5, 6, 4});

思路分析：

链表是以逆序存储数字，这大大方便了我们相加，因为加法运算也是从个位开始的
我们按照顺序遍历两个链表，对每一位进行相加，同时我们需要保存进位，将运算结果存入新的链表中，如图
image.png
遍历链表可以使用迭代，也可以使用递归，我们首先考虑性能较好的迭代法。通过创建一个head头来存放新的链表，初始化一个进位器add，创建current指针指向head，每次迭代完之后让current = current.next，同时也对l1和l2 进行同样的操作，这样三者迭代的进度一致，如上图所示，具体实现如下

Java解法一：指针迭代

  1. public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  2.     // 创建一个表头，用来存放接下里的链表
  3.     ListNode head = new ListNode(0);
  4.     // 创建一个指针Node，初始指向head，循环一次后会指向nextNode，以此延长head长度
  5.     ListNode current = head;
  6.     // 设置一个进位器
  7.     int add = 0;
  8.     // 如果next都等于null，遍历完毕跳出循环结束
  9.     while(l1 != null || l2 != null) {
  10.         int value1 = l1 == null ? 0 : l1.val ;
  11.         int value2 = l2 == null ? 0 : l2.val ;
  12.         int sum = value1 + value2 + add;
  13.         // 利用int的机制保留进位
  14.         add = sum/10;
  15.         // 将当前位的运算结果存入新的链表中
  16.         ListNode newNode = new ListNode(sum%10);
  17.         current.next = newNode;
  18.         // 如果不等于null，更新指针的值指向next
  19.         if (l1 != null) l1 = l1.next;
  20.         if (l2 != null) l2 = l2.next;
  21.         // 更新current指针
  22.         current = current.next;
  23.     }
  24.     // 如果进位器还有值，那么创建一个新的Node插入队尾
  25.     if (add == 1) {
  26.         current.next = new ListNode(add);
  27.     }
  28.     return head.next;
  29. }

复杂度分析：

  • 时间复杂度：O(max(m, n))，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复max(m, n)次。
  • 空间复杂度：O(max(m, n))， 新列表的长度最多为max(m,n) + 1。

    LeetCode用时：

    非会员LeetCode执行这段代码有点慢，实际运行时间其实只有2ms
    image.png

    Java解法二：递归（占用栈空间）

    迭代能搞定的事情，我们递归也能做到，而且代码更加简洁。
    但是递归会占用栈内的大量空间，所以不推荐
    1. public static ListNode addTwoNumbers(ListNode l1, ListNode l2, int add) {
    2.   if (l1 == null && l2 == null && add == 0) return null;
    3.   int sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + add;
    4.   ListNode node = new ListNode(sum % 10);
    5.   node.next = addTwoNumbers(l1 != null ? l1.next : null, l2 != null ? l2.next : null, sum / 10);
    6.   return node;
    7. }

    复杂度分析：

    同上

    LeetCode用时：

    LeetCode 不支持改变方法的入参

java解法三：2次迭代（性能较差）

先遍历一次两个链表，将数据存在hashmap中，然后再来遍历生成新的链表

  1. public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  2.     // 依次遍历两个链表，利用map储存他们的值再来计算
  3.     HashMap<Integer, Integer> map1 = new HashMap<>();
  4.     HashMap<Integer, Integer> map2 = new HashMap<>();
  5.     int index = 1;
  6.     // 如果next都等于null，遍历完毕跳出循环结束
  7.     while(l1 != null || l2 != null) {
  8.         int value1 = l1 == null ? 0 : l1.val ;
  9.         int value2 = l2 == null ? 0 : l2.val ;
  10.         // 如果不等于null，储存当前值
  11.         if (l1 != null) {
  12.             map1.put(index, value1);
  13.             l1 = l1.next;
  14.         }
  15.         if (l2 != null) {
  16.             l2 = l2.next;
  17.             map2.put(index, value2);
  18.         }
  19.         index ++;
  20.     }
  21.     // 获取最大长度
  22.     int max = Math.max(map1.size(),map2.size());
  23.     ListNode head = new ListNode(0);
  24.     ListNode current = head;
  25.     int add = 0;
  26.     // 从map尾部遍历，利用头插法生成新的链表
  27.     for (int i = 1;i <= max;i++){
  28.         Integer integer1 = map1.get(i) == null ? 0 : map1.get(i);
  29.         Integer integer2 = map2.get(i) == null ? 0 : map2.get(i);
  30.         int sum = integer1 + integer2 + add;
  31.         add = sum/10;
  32.         // 尾插法
  33.         ListNode newHead = new ListNode(sum % 10);
  34.         current.next = newHead;
  35.         current = current.next;
  36.     }
  37.     if (add == 1) {
  38.         current.next = new ListNode(add);
  39.     }
  40.     return head.next;
  41. }

复杂度分析：

  • 时间复杂度：O(2 max(m, n))，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复2max(m, n)次。
  • 空间复杂度：O(max(m, n))， 新列表的长度最多为max(m,n) + 1。

    LeetCode用时：

    时间多了一倍

image.png

拓展：如果链表中的数字不是按逆序存储而是正序呢？

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

拓展解法一：逆序迭代（头插法）

按照解法三的思路，先遍历一遍保存两个链表的所有值，然后通过头插法，从尾部向前遍历得到新链表
这里和解法三的区别在于：
解法三是正向遍历，使用了尾插法构建新链表
这里是反向遍历，使用了头插法构建新联表

这里直接遍历或者使用递归都十分繁琐，不做考虑

  1. public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  2.     // 依次遍历两个链表，利用map储存他们的值再来计算
  3.     HashMap<Integer, Integer> map1 = new HashMap<>();
  4.     HashMap<Integer, Integer> map2 = new HashMap<>();
  5.     int index = 1;
  6.     // 如果next都等于null，遍历完毕跳出循环结束
  7.     while(l1 != null || l2 != null) {
  8.         int value1 = l1 == null ? 0 : l1.val ;
  9.         int value2 = l2 == null ? 0 : l2.val ;
  10.         // 如果不等于null，储存当前值
  11.         if (l1 != null) {
  12.             map1.put(index, value1);
  13.             l1 = l1.next;
  14.         }
  15.         if (l2 != null) {
  16.             l2 = l2.next;
  17.             map2.put(index, value2);
  18.         }
  19.         index ++;
  20.     }
  21.     // 获取最大长度
  22.     int max = Math.max(map1.size(),map2.size());
  23.     // 获取长度差值
  24.     int abs = Math.abs(map1.size()-map2.size());
  25.     ListNode current = new ListNode(0);
  26.     int add = 0;
  27.     int abs1 = 0;
  28.     int abs2 = 0;
  29.     // 从map尾部遍历，利用头插法生成新的链表
  30.     for (int i = max;i >=abs;i--){
  31.         Integer integer1 = map1.get(i);
  32.         Integer integer2 = map2.get(i);
  33.         // 由于长度差的存在，可能出现取出为null的情况，补上下标差abs
  34.         // l2 比 l1长时会改变
  35.         abs1 = integer1 == null ? abs : 0;
  36.         // l1 比 l2长时会改变
  37.         abs2 = integer2 == null ? abs : 0;
  38.         integer1 = map1.get(i-abs) == null ? 0 :map1.get(i-abs);
  39.         integer2 = map2.get(i-abs) == null ? 0 :map2.get(i-abs);
  40.         int sum = integer1 + integer2 + add;
  41.         add = sum/10;
  42.         current.val = sum % 10;
  43.         // 头插法
  44.         ListNode newHead = new ListNode(0);
  45.         newHead.next = current;
  46.         current = newHead;
  47.     }
  48.     return current.next;
  49. }

复杂度分析：

  • 时间复杂度：O(max(m, n) +min(m, n) )，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复max(m, n) +min(m, n) 次。
  • 空间复杂度：O(max(m, n))， 新列表的长度最多为max(m,n) + 1。