剑指 Offer II 025. 链表中的两数相加

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20025.%20%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E4%B8%A4%E6%95%B0%E7%9B%B8%E5%8A%A0/README.md

剑指 Offer II 025. 链表中的两数相加

题目描述

给定两个 非空链表 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]

示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

提示：

链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

注意：本题与主站 445 题相同：https://leetcode.cn/problems/add-two-numbers-ii/

解法

方法一

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:s1,s2=[],[]while l1:s1.append(l1.val)l1=l1.nextwhile l2:s2.append(l2.val)l2=l2.nextcarry,nxt=0,Nonewhile s1 or s2 or carry:sm=(s1.pop() if s1 else 0) + (s2.pop() if s2 else 0)+carrycur=ListNode(sm%10,nxt)nxt=curcarry=sm//10return nxt

Java

/*** 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) {Deque<Integer> s1 = new ArrayDeque<>();Deque<Integer> s2 = new ArrayDeque<>();for (; l1 != null; l1 = l1.next) {s1.push(l1.val);}for (; l2 != null; l2 = l2.next) {s2.push(l2.val);}int carry = 0;ListNode dummy = new ListNode();while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {carry += (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());ListNode node = new ListNode(carry % 10, dummy.next);dummy.next = node;carry /= 10;}return dummy.next;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {stack<int> s1;stack<int> s2;for (; l1; l1 = l1->next) s1.push(l1->val);for (; l2; l2 = l2->next) s2.push(l2->val);int carry = 0;ListNode* dummy = new ListNode();while (!s1.empty() || !s2.empty() || carry) {if (!s1.empty()) {carry += s1.top();s1.pop();}if (!s2.empty()) {carry += s2.top();s2.pop();}ListNode* node = new ListNode(carry % 10, dummy->next);dummy->next = node;carry /= 10;}return dummy->next;}
};

Go

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {s1, s2 := arraystack.New(), arraystack.New()for l1 != nil {s1.Push(l1.Val)l1 = l1.Next}for l2 != nil {s2.Push(l2.Val)l2 = l2.Next}carry, dummy := 0, new(ListNode)for !s1.Empty() || !s2.Empty() || carry > 0 {v, ok := s1.Pop()if ok {carry += v.(int)}v, ok = s2.Pop()if ok {carry += v.(int)}node := &ListNode{Val: carry % 10, Next: dummy.Next}dummy.Next = nodecarry /= 10}return dummy.Next
}

Swift

/*** Definition for singly-linked list.* public class ListNode {*     var val: Int*     var next: ListNode?*     init() { self.val = 0; self.next = nil; }*     init(_ val: Int) { self.val = val; self.next = nil; }*     init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }* }*/class Solution {func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {var s1: [Int] = []var s2: [Int] = []var node1 = l1var node2 = l2while let n1 = node1 {s1.append(n1.val)node1 = n1.next}while let n2 = node2 {s2.append(n2.val)node2 = n2.next}var carry = 0let dummy: ListNode? = ListNode(0)while !s1.isEmpty || !s2.isEmpty || carry != 0 {carry += (s1.isEmpty ? 0 : s1.removeLast()) + (s2.isEmpty ? 0 : s2.removeLast())let node = ListNode(carry % 10)node.next = dummy?.nextdummy?.next = nodecarry /= 10}return dummy?.next}
}