2. 两数相加

已解答

中等

相关标签

相关企业

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

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

你可以假设除了数字 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

  • 题目数据保证列表表示的数字不含前导零

public class T2 {
     public static class ListNode {

         int val;ListNode next;
         ListNode() {
         }
         ListNode(int val) {
             this.val = val;
         }
         ListNode(int val, ListNode next) {
             this.val = val; this.next = next;
         }
         @Override
         public String toString() {
             return "ListNode{" +
                     "val=" + val +
                     ", next=" + next +
                     '}';
         }

     }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
         ListNode head = new ListNode(0);
         ListNode cur = head;
         int carry = 0;
         while (l1 != null || l2 != null) {
             int x = l1 == null ? 0 : l1.val;
             int y = l2 == null ? 0 : l2.val;
             int sum = x + y + carry;
             carry = sum / 10;
             cur.next = new ListNode(sum % 10);
             cur = cur.next;
             if (l1 != null) {
                 l1 = l1.next;
             }
             if (l2 != null) {
                 l2 = l2.next;
             }
             if(carry != 0)
             {
                 cur.next = new ListNode(carry);
             }
         }
         return head.next;
    }
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
        ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
        ListNode listNode = new T2().addTwoNumbers(l1, l2);
        System.out.println(listNode.toString());
    }

}

这道题要求我们对两个非空的链表进行相加，返回一个新的链表表示它们的和。链表中的每个节点都存储一个数字的一位，且数字是按逆序方式存储的。

我们可以使用一个循环来遍历两个链表，同时对应位置的数字相加，并考虑进位的情况。具体步骤如下：

  1. 初始化一个新的链表头节点 head 和一个指针 cur，同时初始化进位 carry 为 0。

  2. 遍历两个链表，对应位置的数字相加并加上进位，得到和 sum 和新的进位 carry。

  3. 创建一个新的节点存储 sum % 10，并将其连接到新链表的末尾。

  4. 更新指针 cur 指向新链表的末尾，并更新两个输入链表的指针。

  5. 如果遍历结束后还有进位，需要在新链表的末尾再添加一个节点存储进位值。

  6. 返回新链表的头节点 head.next。

以上就是对两数相加的简单过程的解释。