计算值的总和中的链接列表 [英] Calculating the Sum of values in a linked list
问题描述
所以我就最近一个编程问题，在接受记者采访时。
有2链表，每个节点的存储从1至9的值（指示数之一索引）。因此，123将是一个链表1-> 2-> 3
现在的任务是创建一个功能：
静态一个LinkedListNode getSum（一个LinkedListNode一个，一个LinkedListNode B）
这将返回值的总和在2链表arguements
如果数组a是：1-> 2-> 3-> 4
和数组b为：5> 6> 7> 8
答案应该是：6> 9> 1> 2
下面是我的算法：
穿过在a和b的每个节点，得到的值以整数和添加它们。创建一个新的链表的这些值。
下面是code：它运行一个复杂性为O（n）的约我承担。一旦通过每个阵列输入和一旦创建输出阵列
任何改进？更好的算法...或code改进
公共类一个LinkedListNode {
一个LinkedListNode下一个;
int值;
公众一个LinkedListNode（int值）{
THIS.VALUE =价值;
this.next = NULL;
}
静态INT的getValue（一个LinkedListNode节点）{
int值= node.value;
而（node.next！= NULL）{
节点= node.next;
值=数值* 10 + node.value;
}
返回值;
}
静一个LinkedListNode getSum（一个LinkedListNode一个，一个LinkedListNode B）{
一个LinkedListNode答案=新一个LinkedListNode（0）;
一个LinkedListNode ANS =回答;
INT AVAL =的getValue（一）;
INT BVAL =的getValue（B）;
INT结果= AVAL + BVAL;
而（结果大于0）{
INT LEN =（int）的Math.pow（（双）10，
（双）将String.valueOf（结果）.length（） - 1）;
INT VAL =结果/ len个;
ans.next =新一个LinkedListNode（VAL）;
ANS = ans.next;
结果=结果 - VAL * len个;
}
返回answer.next;
}
}
我已经看到了这个问题的其他解决方案涉及通过迭代向后在两个输入列表中，同时加入的每个元素，当您去打造返回列表增量一个新的列表。这样就比较复杂了，因为你要添加的每个元素和处理携带接管。
如果数组a是：1-> 2-> 3-> 4
和数组b为：5> 6> 7> 8
迭代向后
然后4 + 8 = 12（返回列表电流= 2）
携带1
（1）+ 3 + 7 = 11（返回列表= 1> 2）
携带1
（1）+ 2 + 6 = 9（返回列表= 9 - > 1 - > 2）
1 + 5 = 6（返程列表= 6-> 9> 1> 2）
您可以通过使用堆栈来获取LIFO自然向后遍历如果列表只单链表实现这一点。
So I got a programming question at an interview recently.
There are 2 linked lists, each node's store a value from 1 through 9 (indicating one index of the number). Hence 123 would be a linked list 1->2->3
The task was to create a function:
static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)
that would return the sum of the values in the 2 linked list arguements.
If the array a is: 1->2->3->4
And the array b is: 5->6->7->8
The answer should be: 6->9->1->2
Here is my algorithm:
Go through each node in a and b, get the values as an integer and add them. Create a new linked list with the those values.
Here is the code: It runs with a complexity of O(n) roughly I assume. Once through each of the array inputs and once to create the output array.
Any improvements? Better algorithms... or code improvements
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;
}
}
Other solutions I have seen for this problem involve building the returned list incrementally by iterating backwards over both the input lists at the same time adding each element as you go to a new list. That way is more complicated because you have to add each element and deal with carry overs.
If the array a is: 1->2->3->4
And the array b is: 5->6->7->8
Iterate backwards
Then 4 + 8 = 12 (returned list current = 2)
carry the 1
(1) + 3 + 7 = 11 (returned list = 1-> 2)
carry the 1
(1) + 2 + 6 = 9 (returned list = 9 -> 1 ->2 )
1 + 5 = 6 ( return list = 6->9>1->2)
You can implement this by using Stacks to get the LIFO nature to iterate backwards if the list is only singly linked.
这篇关于计算值的总和中的链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
