JAVA练习296- 两数相加

题目概览

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

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

你可以假设除了数字 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
• 题目数据保证列表表示的数字不含前导零

来源：2. 两数相加 - 力扣（LeetCode）

解题分析

方法：模拟

两个链表同时遍历，两个节点值相加，因为可能前一个节点有进位的情况，因此用变量 carry 记录，相加两个节点的值再加上carry，令和为 sum，新节点值为 sum % 10，新 carry 为 sum / 10，依次遍历即可。注意，如果一个节点遍历完了，就令它的值为0继续遍历，直到 sum 为 0。

时间复杂度：O(m+n)
空间复杂度：O(1) （返回值不计入计算）

/** * 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) { ListNode a = l1, b = l2, temp = new ListNode(); ListNode result = temp; int carry = 0; while(a != null || b != null) { int valA = 0; int valB = 0; if (a != null) { valA = a.val; a = a.next; } if (b != null) { valB = b.val; b = b.next; } int sum = valA + valB + carry; carry = sum / 10; temp.next = new ListNode(sum % 10); temp = temp.next; } if (carry > 0) { temp.next = new ListNode(carry); } return result.next; } }