java - 由链表节点表示的两个数字相加

Question

我正在准备面试。我得到的问题是：两个数字由一个链表表示，其中每个节点包含一个数字。数字以相反的顺序存储，因此 1 的数字位于列表的头部。编写一个函数，将两个数字相加并以链表的形式返回总和。建议的答案分别添加每个数字并保留一个“进位”数字。例如，如果两个数字的第一个数字是“5”和“7”。该算法在结果和的第一位记录“2”，并将“1”作为“进位”添加到结果的第 10 位。但是，我的解决方案是遍历这两个链表，并将它们翻译成两个整数。然后我添加数字并将总和转换为新的链表。不会 我的解决方案是否更直接、更高效？谢谢！

Answer 1

虽然您的解决方案可能更直接，但我认为它实际上并没有更有效。

我假设“正确”的算法是这样的：

1. 弹出两个列表的第一个元素
2. 将它们加在一起（如果有的话，加上进位）并使用个位数创建一个新节点
3. 通过进位（将总和除以 10 得到实际要进位的东西）并重复 1）和 2），每个连续节点都由前一个节点指向。

当我将您的算法与该算法进行比较时，我看到的主要内容是：

1. 在内存方面，您希望在最终链表本身之上创建两个BigIntegers 来存储中间值（我假设您正在使用BigIntegeror 一些等价物Object来避免intor的约束）。long原始算法不使用超过几个ints 来进行中间计算，因此从长远来看，原始算法实际上使用的内存更少。
2. 您还建议您使用BigIntegers 进行所有算术运算，而不是在ints 中。尽管它可能BigInteger真的被优化到不比原始操作慢多少的程度，但我高度怀疑调用BigInteger#add是否比在s上执行+操作更快。int

此外，还有一些值得深思的地方。假设您没有方便的东西BigInteger来存储任意大的整数。然后你将不得不有一些方法来存储任意大的整数，以便你的算法正常工作。在那之后，你基本上需要一种方法来添加任意大的整数来添加任意大的整数，你最终会遇到一个问题，你要么必须做一些类似于原始算法的事情，要么最终使用完全不同的表示形式子程序（哎呀）。

Answer 2

（假设你的意思是“整数” int。）

您的解决方案不会超出可以容纳在 中的数字int，而原始解决方案仅受可用内存量的限制。

就效率而言，您的解决方案没有什么比原来的更高效。

Answer 3

当然，您的解决方案更易于描述，并且在某些情况下可能会提出一个论点，即在与大型团队合作时，您的解决方案生成的代码的可读性会更好。

但是，大多数时候 - 他们建议的答案是内存效率更高，并且可能 CPU 效率更高。

您建议通过第一个链表，将其存储为数字（+1 商店）。通过第二个，将其存储为一个数字（+1 商店）。添加 2 个数字，保存结果（+1 存储）。将此数字转换为链表并保存（+1 存储）

他们的解决方案包括遍历第一个和第二个链表，同时写入第三个链表，并将其存储为新链表（+1 存储）

这是 +1 商店，而不是您的 +4 商店。这可能看起来不多，但如果我们尝试同时添加 n 对数字（在分布式系统或其他系统上），您将看到 4n 个商店，而不仅仅是 n 个商店。这可能是一件大事。