LeetCode445-两数相加II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/add-two-numbers-ii/

中文链接：https://leetcode-cn.com/problems/add-two-numbers-ii/

题目详述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:

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

示例:

1
2
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

题目详解

  • LeetCode2-两数相加中的链表是逆序存储的，而本题的链表是正序存储的。
  • 由于输入链表不能修改，不能翻转，为了模拟从低位到高位相加，可以运用栈来存储两个链表中的值。然后依次弹出栈顶实现从低位到高位相加。
  • 一般来说，链表是采用尾插法构建的。本题采用尾插法最后还需要翻转一次链表，可以采用头插法构建链表，这样就不用翻转链表了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00445 {

    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);
        }
        ListNode head = null;
        int carry = 0;
        while (!s1.isEmpty() || !s2.isEmpty() || carry > 0) {
            carry += (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
            ListNode h = new ListNode(carry % 10);
            h.next = head;
            head = h;
            carry /= 10;
        }
        return head;
    }
}