java - 计算2个链表中的值总和

This question already has answers here:

Calculating the Sum of values in a linked list
（5个答案）

This question was migrated from Software Engineering Stack Exchange because it can be answered on Stack Overflow. Migrated6年前Learn more。
所以我在最近的一次面试中遇到了一个编程问题。
有两个链表，每个节点存储一个从1到9的值（表示数字的一个索引）。因此123将是链表1->2->3
任务是创建一个函数：
static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)
这将返回两个链表参数中的值之和。
如果数组A是：1->2->3->4
数组b是：5->6->7->8
答案应该是：6->9->1->2
以下是我的算法：
遍历a和b中的每个节点，将值作为整数进行相加。使用这些值创建一个新的链接列表。
下面是代码：它运行的复杂性（O）大约是我假设的。一次通过每个数组输入，一次创建输出数组。
有什么改进吗？更好的算法或代码改进

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

最佳答案

让我试一试…

static LinkedListNode getSum(LinkedListNode a, LinkedListNode b) {
  //some checks first if any computation will be needed at all
  if(a == null) {
    if(b == null)
      return null;
    else
      return b;
  } else if (b == null)
    return a;

  //initialize the variables
  LinkedListNode stacka = null;
  LinkedListNode stackb = null;
  LinkedListNode ans = null;
  LinkedListNode temp = null;

  //move the contents of a & b into stacka & stackb respectively at the same time
  //best case is when a & b are of equal size
  //worst case is when the size of a & b are worlds apart.
  while(a != null || b != null){
    if(a != null) {
      if(stacka == null){
        stacka = new LinkedListNode(a.value);
      } else {
        temp = new LinkedListNode(a.value);
        temp.next = stacka;
        stacka = temp;
      }
    }

    if(b != null) {
      if(stackb == null){
        stackb = new LinkedListNode(b.value);
      } else {
        temp = new LinkedListNode(b.value);
        temp.next = stackb;
        stackb = temp;
      }
    }

    if(a != null) a = a.next;
    if(b != null) b = b.next;
  }

  int remainder = 0;
  //just pop off the stack then merge! also, don't forget the remainder~
  while(stacka != null || stackb != null){
    //pop from the top of the stack
    int i = ((stacka == null) ? 0 : stacka.value) + ((stackb == null) ? 0 : stackb.value) + remainder;

    //set the value of the remainder if any as well as the value of i
    remainder = i / 10;
    i %= 10;

    temp = new LinkedListNode(i);
    if(ans == null) {
      ans  = temp;
    } else {
      temp.next = ans;
      ans = temp;
    }
    if(stacka != null) stacka = stacka.next;
    if(stackb != null) stackb = stackb.next;
  }
  return ans;
}

因为我没有使用getValue（）函数，所以在最好的情况下应该是o（2n）左右。
我在这里做的是使用linkedlistnode作为堆栈，在反转节点时临时存储这些节点，然后一次弹出一个值来填充输出linkedlistnode。
最后，这两种算法仍然在o（n）之下，因此差异可以忽略不计。
如果我有时间的话，我会试着做一个递归的版本。
抱歉，如果我没有在一些if-else语句中添加大括号，很难使用应答表将它们标记出来

关于java - 计算2个链表中的值总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19328095/