力扣经典150题第五十七题：两数相加
力扣经典150题第五十七题：两数相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
示例
示例 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
- 题目数据保证列表表示的数字不含前导零
解题思路
本题可以通过模拟加法的方式求解，从链表的头节点开始逐位相加，注意进位的处理。具体步骤如下：
- 创建一个新的链表
dummyHead作为结果链表的头节点，并初始化进位carry为 0。 - 遍历输入的两个链表
l1和l2，同时对应位置上的节点进行相加，如果某个链表已经遍历完成，则对应位置上的数字视为 0。 - 将两个节点值与进位相加，并更新进位。
- 将相加结果的个位数作为新节点的值，并将新节点连接到结果链表的尾部。
- 更新指针，继续遍历下一个节点，直到两个链表都遍历完毕。
- 如果最后还有进位，则在结果链表的尾部添加一个值为进位值的新节点。
- 返回结果链表的头节点。
以下是 Java 代码示例：
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class AddTwoNumbers {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
public static void main(String[] args) {
AddTwoNumbers solution = new AddTwoNumbers();
// 创建示例链表
ListNode l1 = new ListNode(2);
l1.next = new ListNode(4);
l1.next.next = new ListNode(3);
ListNode l2 = new ListNode(5);
l2.next = new ListNode(6);
l2.next.next = new ListNode(4);
// 测试示例
ListNode result = solution.addTwoNumbers(l1, l2);
while (result != null) {
System.out.print(result.val + " ");
result = result.next;
}
// 输出：7 0 8
}
}
该代码通过模拟加法的方式，从链表的头节点开始逐位相加，具有时间复杂度 O(max(m, n)) 和空间复杂度 O(max(m, n)) 的特性。本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-06-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
