445. 两数相加 II

难度: 中等

来源: 每日一题 2023.07.03

---

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

 

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

提示：

链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

/**
 * Definition for singly-linked list.
 * public 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) {
    }
}

分析与题解

---

• 入栈求解法

  相对于 2.两数相加 题来说,这个题就是一个高低位反转的问题. 这里我的思路是需要使用到 栈 的先进后出,后进先出的特性来做这个题.

  • 先把l1 和 l2 所有链表节点入栈到 l1Stack 和 l1Stack.

  • 然后 l1Stack 和 l1Stack 两个栈的元素尽量保持同步出栈,然后构建链表即可.

  题解代码如下所示.

  /**
  * Definition for singly-linked list.
  * public 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) {
          Stack<Integer> l1Stack = new Stack();
          Stack<Integer> l2Stack = new Stack();
          // 入栈
          while(l1 != null || l2 != null) {
              if (l1 != null) {
                  l1Stack.push(l1.val);
                  l1 = l1.next;
              }
              if (l2 != null) {
                  l2Stack.push(l2.val);
                  l2 = l2.next;
              }
          }
          // 构建链表
          ListNode resultNode = null;
          ListNode nextNode = null;
          int carryNumber = 0;
          // 栈中含有元素 或者 进位不为空, 进位不为空;
          while(!l1Stack.empty() || !l2Stack.empty() || carryNumber != 0) {
              int value = 0;
              if (!l1Stack.empty()) {
                  value += l1Stack.pop();
              }
              if (!l2Stack.empty()) {
                  value += l2Stack.pop();
              }
              if (carryNumber != 0) {
                  value += carryNumber;
                  carryNumber = 0;
              }
              if (value/10 > 0) {
                  carryNumber = value/10;
                  value = value%10;
              }
              if (resultNode == null) {
                  resultNode = new ListNode(value);
                  resultNode.next = nextNode;
              } else {
                  nextNode = resultNode;
                  resultNode = new ListNode(value);
                  resultNode.next = nextNode;
              }
          }
          return resultNode;        
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(max(m ,n)), 其中 n 和 m 为 l1 和 l2 的长度。
  • 空间复杂度: O(1)

  结果如下所示.

  

• 反转求解法

  反转求解法就是先利用 反转链表 和 2.两数相加 的结合解决这个题目的题解.

  • 反转链表 整体实现比较简单.

    public ListNode reverseNode(ListNode node){
        if(node.next==null) return node;
        ListNode prev=null;
        ListNode cur=node;
        ListNode curBehind=null;
        while(cur!=null){
            curBehind=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curBehind;
        }
        return prev;
    }
    

  • 然后当我们反转 l1 和 l2 之后, 按照 2.两数相加 的思路来题解即可. 当然了,需要把 求解的链表再次反转 即可完成整体题目.

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
    
        ListNode head1=reverseNode(l1);
        ListNode head2=reverseNode(l2);
        ListNode res=new ListNode();
        ListNode temp=res;
        int val1=0,val2=0;
        int carry=0;
        while(head1!=null||head2!=null){
            val1=head1==null?0:head1.val;
            val2=head2==null?0:head2.val;
            res.next=new ListNode( (val1+val2+carry)%10 );
            carry=(val1+val2+carry)/10;
            res=res.next;
            head1=head1==null?null:head1.next;
            head2=head2==null?null:head2.next;
        }
        if(carry!=0)res.next=new ListNode(carry);
        return reverseNode(temp.next);
    }
    

  整体代码如下所示.

  /**
  * Definition for singly-linked list.
  * public 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) {
          if(l1==null)return l2;
          if(l2==null)return l1;
  
          ListNode head1=reverseNode(l1);
          ListNode head2=reverseNode(l2);
          ListNode res=new ListNode();
          ListNode temp=res;
          int val1=0,val2=0;
          int carry=0;
          while(head1!=null||head2!=null){
              val1=head1==null?0:head1.val;
              val2=head2==null?0:head2.val;
              res.next=new ListNode( (val1+val2+carry)%10 );
              carry=(val1+val2+carry)/10;
              res=res.next;
              head1=head1==null?null:head1.next;
              head2=head2==null?null:head2.next;
          }
          if(carry!=0)res.next=new ListNode(carry);
          return reverseNode(temp.next);
      }
      public ListNode reverseNode(ListNode node){
          if(node.next==null) return node;
          ListNode prev=null;
          ListNode cur=node;
          ListNode curBehind=null;
          while(cur!=null){
              curBehind=cur.next;
              cur.next=prev;
              prev=cur;
              cur=curBehind;
          }
          return prev;
      }
  }    
  

  复杂度分析:

  • 时间复杂度: O(max(m ,n)), 其中 n 和 m 为 l1 和 l2 的长度。
  • 空间复杂度: O(1), 都是固定个数的变量.

  结果如下所示.