将表示为链表的数字相乘

Question

我已经尝试解决这个问题一段时间了，现在，但是 none 我的方法到目前为止都奏效了。

给你两个表示大数的链表，其中链表的头部表示最低有效数字。 Return 一个新列表，它存储两个列表相乘的结果。

我已经尝试了一种算法，该算法适用于第一个列表是一个数字，但不会超过这个数字。

初始化一个新列表。
初始化一个进位。
当节点 1 不为空时：
当节点 2 不为空时：
如果节点3的next不为null，则将它的值加入进位；
设置节点3的next为节点1 *节点2的值+进位。
将节点 2 设置为下一个，将节点 3 设置为下一个。
设置在第 4 节时结束
将节点 1 设置为节点 1 的下一个。
在第 3 节设置时结束。
Return 列表设置在第 1 部分。

这显然有问题。我还尝试为第一个循环的每次迭代设置一个“powCounter”，并将该值乘以 10 的 powCounter 次方。但这也没有用。

非常感谢任何帮助！

Answer 1

像在纸上那样做。

想必在派你写multiply(a, b)之前，他们就已经让你写add(a, b)了吧？所以用那个。

您说您已经编写了与单个数字相乘的逻辑，所以我们调用它 multiplySingle(a, digit)。

您还需要一种辅助方法，例如shiftLeft(a, n)，它将 n 0 添加到数字的末尾，即添加到列表的开头。例如。 shiftLeft([4,3,2,1], 2)应该return[0,0,4,3,2,1]，意思是1234 * 10² = 123400.

所以，在纸面上你会像这样将 123 乘以 456：

123 * 456
    45600  =  1 * 456 * 100  =  shiftLeft(multiplySingle([6,5,4], 1), 2)
     9120  =  2 * 456 * 10   =  shiftLeft(multiplySingle([6,5,4], 2), 1)
     1368  =  3 * 456 * 1    =  shiftLeft(multiplySingle([6,5,4], 3), 0)
    =====
    56088  = 45600 + 9120 + 1368  =  add(add([0,0,6,5,4], [0,2,1,9]), [8,6,3,1])

祝你编写代码顺利。

仅供参考： shiftLeft() 方法的想法基于内置 BigInteger 和 BigDecimal 类.

BigInteger shiftLeft(int n)

Returns a BigInteger whose value is (this << n). The shift distance, n, may be negative, in which case this method performs a right shift. (Computes floor(this * 2ⁿ).)
BigDecimal movePointRight(int n)

Returns a BigDecimal which is equivalent to this one with the decimal point moved n places to the right. If n is non-negative, the call merely subtracts n from the scale. If n is negative, the call is equivalent to movePointLeft(-n). The BigDecimal returned by this call has value (this × 10ⁿ) and scale max(this.scale()-n, 0).

将表示为链表的数字相乘

Multiply numbers represented as Linked List

java

loops

recursion

linked-list

biginteger