剑指OfferII025.链表中的两数相加

---

comments: true edit_url: github /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 题相同： leetcode /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.next while l2: s2.append(l2.val) l2=l2.next carry,nxt=0,None while s1 or s2 or carry: sm=(s1.pop() if s1 else 0) + (s2.pop() if s2 else 0)+carry cur=ListNode(sm%10,nxt) nxt=cur carry=sm//10 return 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 = node carry /= 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 = l1 var node2 = l2 while let n1 = node1 { s1.append(n1.val) node1 = n1.next } while let n2 = node2 { s2.append(n2.val) node2 = n2.next } var carry = 0 let 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?.next dummy?.next = node carry /= 10 } return dummy?.next } }