链表中的两数相加
# 📃 题目描述
题目链接:
- 剑指 Offer II 025. 链表中的两数相加 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 445. 两数相加 II - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例1:
输入:l1 = [7,2,4,3], l2 = [5,6,4]
输出:[7,8,0,7]
示例 2:
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[8,0,7]
# 🔔 解题思路
最直观的想法,根据链表求出整数,然后直接将两个整数相加,最后把结果用链表表示。这种思路的最大的问题是没有考虑到整数有可能会溢出。当链表较长时,表示的整数很大,可能会超出int甚至long的范围,如果根据链表求出整数就有可能会溢出
解决这个问题的办法是把表示整数的链表反转。反转之后的链表的头节点表示个位数,尾节点表示最高位数。此时从两个链表的头节点开始相加,就相当于从整数的个位数开始相加。
在做加法时还需要注意的是进位。如果两个整数的个位数相加的和超过10,就会往十位数产生一个进位。在下一步做十位数相加时就要把这个进位考虑进去。
总体来说就是三步走:
- 先把两个表示整数的链表反转
- 再在两个反转之后的链表中逐个节点实现加法
- 最后把表示和的链表反转
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
// 1 先把两个表示整数的链表反转
ListNode head1 = reverseList(l1);
ListNode head2 = reverseList(l2);
// 2 再在两个反转之后的链表中逐个节点实现加法
ListNode reversedHead = addReversed(head1, head2);
// 3 最后把表示和的链表反转
return reverseList(reversedHead);
}
// 俩链表从前往后相加,并返回第一个节点
private ListNode addReversed(ListNode head1, ListNode head2) {
// 虚拟头节点
ListNode dummy = new ListNode(0);
// 工作指针
ListNode cur = dummy;
// 进位
int carry = 0;
while (head1 != null || head2 != null) {
int sum = (head1 == null ? 0 : head1.val)
+ (head2 == null ? 0 : head2.val)
+ carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
cur.next = new ListNode(sum);
cur = cur.next;
head1 = head1 == null ? null : head1.next;
head2 = head2 == null ? null : head2.next;
}
// 处理最后一个进位
if (carry > 0) {
cur.next = new ListNode(carry);
}
return dummy.next;
}
private ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
// 保存 cur 的后继节点
ListNode successor = cur.next;
// 更改 next 指针
cur.next = pre;
// 进入下一个节点
pre = cur;
cur = successor;
}
// 返回反转后链表的头节点
return pre;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10