计算链接列表中的值总和

Question

最近在一次采访中我遇到了编程问题。

有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;
    }
}

Answer 1

我针对该问题看到的其他解决方案包括通过向后遍历两个输入列表来逐步构建返回的列表，同时在转到新列表时添加每个元素。这种方式更加复杂，因为您必须添加每个元素并处理结转。

如果数组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）

如果列表仅是单个链接，则可以通过使用Stacks来实现LIFO性质以向后迭代，从而实现此目的。