algorithm - 给数字链表加 1

Question

给定一个链表，使得每个节点都是数字中的一个数字。

例如：如果 number 为 1234，则对应的链表为：

1 -> 2 -> 3 -> 4 -> [\]

问题是在这个数字上加 1。所以输出将是：

1 -> 2 -> 3 -> 5 -> [\]

我们可以在 O(n) 时间和 O(n) 空间中递归地完成它。是否可以优化 O(logn) 时间复杂度的解决方案？

更新： n 是总位数。

Answer 1

不，只要您没有额外的数据结构。

由于列表中的最后一个节点总是会改变，并且任何算法到达那里都需要 O(n) 时间（如果你没有额外的数据结构，你必须追逐整个列表），这使得 O(n) 作为你的下限边界。

Answer 2

在执行操作之前，您必须遍历每个数字，没有其他方法，但由于您知道元素的总数，因此您可以编写所有移动操作，例如 head->next->next->next...在同一行而不是 for 循环中。这将加快进程，因为将避免运行 for 循环的超载时间复杂度。

Answer 3

是什么n？如果n是数字中的位数，我认为不可能有O(log(n))解决方案。

如果 n 是数字本身，那么位数已经是O(log(n))。