LeetCode刷题笔记_[2]两数相加

language: java

knowledge: listNode

题目：

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一

提供的链表范围为[1, 100]，则最少会有一个节点，新建一个head链表用于保存结果，则第一个节点的值为l1.val + l2.val。
创建一个cur引用head链表，用于操作head链表（若直接使用head，则会输出head最后节点）
使用一个while循环遍历链表，判断条件为l1、l2两链表的下一节点都不为空while(l1.next != null || l2.next != null)。
判断两链表的下一节点是否为空，若不为空则将当前节点后移，若为空则将当前直为空节点：l1 = l1.next != null ? l1.next : new ListNode;
两链表的节点值之和可能会大于9，此时则会向后产生一个进位（链表节点值范围[0, 9]，节点值和范围为[0, 18]）。故cur的下一个节点值为l1.val + l2.val + cur.val / 10)。
此时，cur的下一个节点的值已经确定，但cur当前节点的值可能不合规范（[0, 9]），所以要对cur取余：cur.val %= 10。（因为cur不一定会大于10，所以不可使用-10来计算当前节点应存储的值。
将cur移向下一个节点。
当while循环结束，代表两个链表都已遍历完毕，如下：

此时，cur的最后一个节点仍可能大于9，比如l1和l2都是单节点链表，那么就不会进入while循环，而计算之后得到cur.val = 10，不合规范，需要执行一次5、6。

代码如下：

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      ListNode head = new ListNode(l1.val + l2.val);
      ListNode cur = head;
      while (l1.next != null || l2.next != null) {
            l1 = l1.next != null ? l1.next : new ListNode();
            l2 = l2.next != null ? l2.next : new ListNode();
            cur.next = new ListNode(l1.val + l2.val + cur.val / 10);
            cur.val %= 10;
            cur = cur.next;
      }
      if (cur.val >= 10) {
            cur.next = new ListNode(cur.val / 10);
            cur.val %= 10;
      }
      return head;
   }
}

思路二

首先按照链表顺序依次相加，结果都赋给l1，如果大于9就向下位进1，直到有一方链表到达末尾。
判断l2结果是否非空，如果不为空则说明l2更长，就把l2接续到l1末端，然后判断l1剩余元素是否仍有可能发生进位。
当完成前n位的计算后，判断cur.val是否大于9，是就需要新建一个节点存储最高位进位值，最后返回对l1的引用对象。

此方法由于没有新建链表，只是对l1进行引用、操作，故空间复杂度为O(1)，时间复杂度为O(max(l1, l2))。

JAVA学习网

分类

LeetCode刷题笔记_[2]两数相加

题目：

思路一

思路二