该函数将两个整数作为字符串，假设为“ 123”和“ 456”，它们以连续的顺序解析为它们自己的链接列表。因此，第一个为3-> 2-> 1，第二个为6-> 5-> 4。
我已经初始化了这些链表，但是如何将它们相乘以获得乘积123 * 456？我不知道如何处理此问题，特别是因为它们是以相反的顺序解析的。
我不允许编辑这些链接列表。但是，我可以将它们解析为两个虚拟列表。
感谢您的任何帮助。
public static BigInteger multiply(BigInteger first, BigInteger second) {
/* IMPLEMENT THIS METHOD */
// following line is a placeholder for compilation
return null;
}
// where earlier in the class
public BigInteger() {
negative = false;
numDigits = 0;
front = null;
}
// and in the same package
public class DigitNode {
int digit;
DigitNode next;
DigitNode(int digit, DigitNode next) {
this.digit = digit;
this.next = next;
}
public String toString() {
return digit + "";
}
}
考虑如何手工乘法：
456
x 123
-----
1368
+ 9120
+ 45600
--------
56088
[使用列表，3->2->1和6->5->4，将3和6相乘，得到18的乘积。然后，将3和5相乘，得到15的乘积。但是必须将其乘以10，因为5位在第二位置。然后将3和4相乘得到12，再乘以100。所以顺序为：
3*6 = 18
3*5*10 = 150
3*4*100 = 1200
总和得到1368。
然后您从2开始。但是它处于第二位置，所以实际上是20：
10*2*6 = 120
10*2*5*10 = 1000
10*2*4*100 = 8000
----
9120
并重复第三个数字，1：
100*1*6 = 600
100*1*5*10 = 5000
100*1*4*100 = 40000
-----
45600
[添加您的局部文件（45600 + 9120 + 1368）= 56088
您可以使用两个嵌套循环在链接列表上进行迭代。看起来像这样：
total = 0
l1 = list1.head
l1Multiplier = 1
while l1 != null
l2 = list2.head
l2Multiplier = 1
l1Sum = 0
while l2 != null
prod = l1Multiplier * l1.data * l2.data * l2Multiplier
l1Sum = l1Sum + prod
l2Multiplier = l2Multiplier * 10
l2 = l2.next
end while
total = total + l1Sum
l1Multiplier = l1Multiplier * 10
end while
// at this point, the result is in the total variable.
// You can extract the digits into another linked list.
这不是最有效的方法，但是我怀疑这里的目标不是提出最有效的算法，而是学习如何遍历链表。
如果您对更高效的算法感兴趣，请查看Karatsuba algorithm。