java计算2个链表中的值之和
所以我最近在一次采访中遇到了一个编程问题
有两个链表,每个节点存储一个从1到9的值(表示数字的一个索引)。因此123将是一个链表1->;2->;三,
任务是创建一个函数:
static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)
这将返回两个链表参数中的值之和
如果阵列a为:1->;2->;3->;四,
而数组b是:5->;6->;7->;八,
答案应该是:6->;9->;1->;二,
以下是我的算法:
遍历a和b中的每个节点,将值作为整数进行相加。用这些值创建一个新的链表
代码如下:我假设它的运行复杂度大致为O(3n)。一次通过每个数组输入,一次创建输出数组
有什么改进吗?更好的算法。。。或代码改进
public class LinkedListNode {
LinkedListNode next;
int value;
public LinkedListNode(int value) {
this.value = value;
this.next = null;
}
static int getValue(LinkedListNode node) {
int value = node.value;
while (node.next != null) {
node = node.next;
value = value * 10 + node.value;
}
return value;
}
static LinkedListNode getSum(LinkedListNode a, LinkedListNode b) {
LinkedListNode answer = new LinkedListNode(0);
LinkedListNode ans = answer;
int aval = getValue(a);
int bval = getValue(b);
int result = aval + bval;
while (result > 0) {
int len = (int) Math.pow((double) 10,
(double) String.valueOf(result).length() - 1);
int val = result / len;
ans.next = new LinkedListNode(val);
ans = ans.next;
result = result - val*len;
}
return answer.next;
}
}
# 1 楼答案
首先,浏览两个列表,翻转箭头方向,以内存中的最后一个节点结束。这是线性时间和恒定空间
现在你有了一对链表,代表从最低到最高的数字。再次浏览列表,创建新的链接列表,并在运行时向后翻转箭头。这是线性时间和线性空间(对于新列表)
# 2 楼答案
让我试一试
因为我没有使用getValue()函数,所以在最好的情况下应该是O(2n)左右。 我在这里做的是将LinkedListNode用作堆栈,在反转节点时临时存储它们,然后一次弹出一个值来填充输出LinkedListNode
最后,这两种算法仍然处于O(n)之下,因此差异可以忽略不计
如果有时间的话,我会试着做一个递归版本
另外,如果我没有在我的if-else语句中添加大括号,很抱歉,很难使用答案表单来标记它们
# 3 楼答案
最初的问题是Java,但这里有一个非常简单的Scala解决方案。它在列表中留下了0,因此它们的长度相同。然后,它将列表拉到一起,这样我们就有了一个单一的成对列表。最后,它将沿着进位值从右向左添加对。(就像你在一年级学习如何添加数字一样。)它展示了我们如何使用函数技术快速解决问题,并使用少量代码:
# 4 楼答案
它可以通过从后到前构建生成的链表进行优化:
这避免了重复计算。战俘呼叫
我认为你使用的整体算法应该是最快的。想到的另一种方法是对每对数字进行某种带进位的加法运算(即“手动”进行加法),但这很可能会更慢
# 5 楼答案
通常,在这些类型的练习中,人们希望在不首先转换为更常见的中间形式(如整数)的情况下执行操作。我想问的下一个问题是,“如果数字是100位长怎么办?”尝试仅使用链表来解决这个问题,尽管为了提供合理的运行时间,可能必须反转操作数的方向