我最近在一次面试中遇到了一个编程问题。
有2个链表。每个节点存储一个从 1 到 9 的值(表示数字的一个索引)。因此 123 将是一个链表 1->2->3
任务是创建一个函数:
static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)
这将返回 2 个链表参数中的值的总和。
如果数组a是:1->2->3->4
数组 b 为:5->6->7->8
答案应该是:6->9->1->2
这是我的算法:
遍历 a 和 b 中的每个节点,以整数形式获取值并将它们相加。使用这些值创建一个新的链表。
这是代码:我假设它以 O(n) 的复杂度运行。一次通过每个数组输入,一次创建输出数组。
有什么改进吗?更好的算法......或代码改进
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;
}
}