题目
原题链接:剑指 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Deque<Integer> stack1 = new ArrayDeque<Integer>(); Deque<Integer> stack2 = new ArrayDeque<Integer>(); while (l1 != null) { stack1.push(l1.val); l1 = l1.next; } while (l2 != null) { stack2.push(l2.val); l2 = l2.next; } int carry = 0; ListNode ans = null; while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) { int a = stack1.isEmpty() ? 0 : stack1.pop(); int b = stack2.isEmpty() ? 0 : stack2.pop(); int cur = a + b + carry; carry = cur / 10; cur %= 10; ListNode curnode = new ListNode(cur); curnode.next = ans; ans = curnode; } return ans; } }
|