2. 两数相加 - 力扣（Leetcode）

题目描述给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 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题目数据保证列表表示的数字不含前导零思路分析两个数字按逆序存储即链表的头节点是个位依次是十位、百位……。相加时我们需要同时遍历两个链表对应位相加并处理进位carry。具体步骤初始化一个哑节点 dummy用于简化结果链表的构建指针 curr 指向它。初始化进位 carry 0。当 l1 不为空、l2 不为空或 carry 不为 0 时循环取 l1 的当前值若为空则为 0l2 的当前值若为空则为 0。计算 sum val1 val2 carry。当前位结果 sum % 10新进位 sum / 10。创建新节点连接到 curr.next移动 curr。移动 l1 和 l2 指针若不为空。返回 dummy.next哑节点的下一个节点即为结果链表的头。复杂度时间复杂度((,))其中 、分别为两个链表的长度最多遍历较长的链表一次。空间复杂度((,))结果链表占用的空间不计递归栈如果算上返回的结果则为 ((,))若不计返回值则 (1)额外空间仅使用几个指针。Code/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val0, ListNode nextnull) { * this.val val; * this.next next; * } * } */public class Solution{public ListNodeAddTwoNumbers(ListNode l1,ListNode l2){ListNode dummynewListNode(0);ListNode currdummy;intcarry0;while(l1!null||l2!null||carry!0){intval1(l1!null)?l1.val:0;intval2(l2!null)?l2.val:0;intsumval1val2carry;carrysum/10;intdigitsum%10;curr.nextnewListNode(digit);currcurr.next;if(l1!null)l1l1.next;if(l2!null)l2l2.next;}returndummy.next;}}作者一清风月一流年链接https://leetcode.cn/problems/add-two-numbers/solutions/3991236/problem-2-liang-shu-xiang-jia-by-yi-qing-e0f4/来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。