c++ - 采访 : Summing numbers in two linked lists

Question

在昨天的一次采访中，有人问我如何对两个包含数字的单向链表的值求和。他们还表示列表的长度可能不等。

我问这个列表是否是反向存储的，因为这是我在 uni 学到的，但他们说不是，它是向前存储的。他们还说我不能简单地反转列表，然后添加，然后反转它以再次向前，因为该选项需要太多处理。我在网上只能找到这种解决方案。

我无法给出答案，即使他们暗示我应该用递归函数来做这件事。

任何人都可以帮助我找出解决方案。这是一份 C++ 工作，我希望如果我被打回电话并且我能够解释我研究了解决方案，他们可能会认为这是一个好兆头。谢谢。

对于那些对求和应该如何工作感到困惑的人，它以这种方式呈现。

列表 1:1->2->9 list 2:1->3

因此，由于数字是向前存储的，因此我需要首先添加 9 和 3(两个列表的末尾)。然后取 1 进位并做 1 + 2 + 1 等。

Answer 1

您计算两个列表的长度。您在较短的列表的开头填充多个 0 数字，以便它们的长度相等。现在你用一个额外的 0 填充两个数字(它将被第一个数字的进位使用。所以 9 + 1 = 10 是可能的)。 您创建了第三个链表，其长度与前两个链表的长度相同。

现在你做这样一个类:

class Digit
{
    public:
    Digit *Next;
    int Dt;
}

还有一个像这样的函数:

int Sum(const Digit* left, const Digit* right, Digit* runningTotal)
{
    int carry = 0;

    if (left->Next != NULL)
    {
        carry = Sum(left->Next, right->Next, runningTotal->Next);
    }

    carry += left->Dt + right->Dt;

    runningTotal->Dt = carry % 10;

    carry /= 10;

    return carry;
}

• 这是“版本 0”。
• 在“版本 1”中，您删除了最后一个进位的额外填充，并且仅在需要时才添加它。
• 在“版本 2”中，您从链接列表的前面删除了不必要的“0”数字。
• 在“版本 3”中，您直接在 Sum 中创建 runningTotal 链表。您仅将运行总计的“头”提供给第一级 Sum。
• 在“版本 4”中，您不是填充较短的 LL，而是传递一个关于要从最长的 LL 跳过的位数的参数(这是最困难的段落)。

还有另一种可能性，更复杂，但不需要预先计算列表的长度。它使用两个递归函数:

第一个递归函数简单地遍历左和右，同时两者都存在。如果两者同时完成，那么您可以像前面的示例一样简单地回滚。

如果其中一个先于另一个完成，那么你可以使用另一个像这样的递归函数(*extraDigits 的初始值为 1):

void SaveRemainingDigits(const Digit *remaining, int *extraDigits, int **buffer)
{
    int currentDigit = *extraDigits - 1;

    *extraDigits = *extraDigits + 1;

    if (remaining->Next)
    {
        SaveRemainingDigits(remaining->Next, extraDigits, buffer);    
    }
    else
    {
        *buffer = (int*)malloc(sizeof(int) * extraDigits);
    }

    (*buffer)[currentDigit] = remaining->Dt;
}

当这个函数最终返回时，我们有一个暂存器，可以从中提取数字和暂存器的长度

我们第一个递归函数的最内层现在必须将最短链表的当前数字与暂存器的最后一位相加，并将最长链表的当前数字放在暂存器中代替刚刚使用的数字.现在您展开递归函数并将暂存器用作圆形数组。完成展开后，将元素添加到 runningTotal 链表中，直接从暂存器中获取它们。

正如我所说，它有点复杂，但在 1-2 小时内我可以将它写成一个程序。

一个例子(没有进位)

1 2 3 4
6 5

你递归前两个元素。所以你有

1-6 (in the first level)
2-5 (in the second level)

现在您看到第二个列表已完成，您可以使用第二个函数。

3 (extraDigit enters as 0, is modified to 1. currentDigit = 0)
4 (extraDigit enters as 1, is modified to 2. currentDigit = 1. 
   malloc of 2 elements,
   buffer[currentDigit] = 4 => buffer[1] = 4)

unroll and we return to the previous row

3 (currentDigit = 0
   buffer[currentDigit] = 3 => buffer[0] = 3)

现在我们回到之前的函数

2-5 (in the second level, 
     with a lengthBuffer == 2, 
     we set index = length(buffer) - 1
     currentDigitTotal = 5 + buffer[index] => currentDigitTotal = 5 + 4
     buffer[index] = 2 => buffer[1] = 2;
     index = (index - 1 + lengthBuffer) % lengthBuffer => index = 0

1-6 (in the first level, 
     with a lengthBuffer == 2, 
     index = 0,
     currentDigitTotal = 6 + buffer[index] => currentDigitTotal = 6 + 3
     buffer[index] = 1 => buffer[0] = 1;
     index = (index - 1 + lengthBuffer) % lengthBuffer => index = 1

now we exited the recursive function. 
In an external function we see that we have a buffer. 
We add its elements to the head of the total.

Our Linked list now is 9-9 and our buffer is 1,2 with index 1

for (int i = 0; i < lengthBuffer; i++)
{
    runningTotal.AddHead(buffer(index));
    index = (index - 1 + lengthBuffer) % lengthBuffer
}