1

所以我最近在一次面试中遇到了一个编程问题。

有 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(3n) 的复杂度运行。一次通过每个数组输入，一次创建输出数组。

有什么改进吗？更好的算法......或代码改进

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

5 回答 5

2

让我试一试...

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) 范围内，所以差异可以忽略不计。

如果我有时间，我稍后会尝试制作一个递归版本。

PS 抱歉，如果我没有在我的一些 if else 语句中添加花括号，那么很难使用答案表来标记它们

于 2013-10-11T20:24:24.837 回答
1

最初的问题是在 Java 中，但这是一个非常简单的 Scala 解决方案。它用 0 填充列表，使它们的长度相同。然后，它将列表压缩在一起，这样我们就有了一个单对列表。最后，它通过一个进位值从右到左添加对。（就像你在一年级学习如何添加数字一样。）它展示了我们如何使用函数技术使用少量代码快速解决问题：

def add(nums1: List[Int], nums2: List[Int]): List[Int] = {
  val nums1Size = nums1.size
  val nums2Size = nums2.size
  val maxSize = nums1Size max nums2Size

  val nums1Padded = List.fill(maxSize - nums1Size)(0) ++ nums1
  val nums2Padded = List.fill(maxSize - nums2Size)(0) ++ nums2
  val zipped = nums1Padded.zip(nums2Padded)

  val (result, carry) = zipped.foldRight((List.empty[Int], 0)) { (curr, r) =>
    val sum = curr._1 + curr._2 + r._2
    ((sum % 10) :: r._1, sum / 10)
  }

  if (carry > 0) carry :: result else result
}
于 2013-10-12T13:08:50.307 回答
0

可以通过从后到前构造生成的链表来优化它：

int aval = getValue(a);
int bval = getValue(b);
int result = aval + bval;
LinkedListNode answer = null;
while (result > 0) {
    int val = result % 10;
    LinkedListNode prev = answer;
    answer = new LinkedListNode(val);
    answer.next = prev;
    result /= 10;
}
if (answer == null) {
    // Assuming you want to return 0 rather than null if the sum is 0
    answer = new LinkedListNode(0);
}
return answer;

这避免了重复的 Math.pow 调用。

我认为您使用的整体算法应该是最快的。想到的一种替代方法是对每对数字进行某种加法运算（即“手动”进行加法），但这很可能会更慢。

于 2013-10-11T18:39:40.977 回答
0

通常在这些类型的练习中，人们期望在不首先转换为更常见的中间形式（如整数）的情况下执行操作。我希望得到的下一个问题是，“如果数字是 100 位长怎么办？” 尝试仅使用链表来解决它，尽管您可能必须反转操作数的方向才能提供合理的运行时间。

于 2013-10-11T18:50:19.940 回答
0

首先，遍历两个列表，翻转箭头的方向并以内存中的最终节点结束。这是线性时间和恒定空间。

现在您有一对链表，它们代表从最低位到最高位的数字。再次遍历列表，创建新的链表并在进行时将箭头向后翻转。这是线性时间和线性空间（对于新列表）。

于 2013-10-12T02:16:14.967 回答