题目概览
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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; } }
