java - 计算链表中值的总和

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(返回列表 current = 2)

携带1

(1) + 3 + 7 = 11(返回列表 = 1-> 2)

携带1

(1) + 2 + 6 = 9(返回列表 = 9 -> 1 ->2)

1 + 5 = 6(返回列表 = 6->9>1->2)

如果列表仅是单链接的，您可以通过使用 Stacks 获得后进先出的特性来实现这一点，以便向后迭代。