面试：对两个链表中的数字求和

Question

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

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

即使他们暗示我应该使用递归函数来完成此操作，我也无法给出答案。

谁能帮我解决这个问题。这是一份 C++ 工作，我希望如果我接到回电并且我能够解释我研究了该解决方案，他们可能会认为这是一个好兆头。谢谢。

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

列表1：1->2->9 列表 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
}

Answer 2

我将以这样的方式解决这个问题

让我们假设这两个列表是：
1->2->7->6->4->3 和
5->7->2

总和为1->2->7 + Sum(6->4->3, 5->7->2)

现在我们创建一个函数，它接受 2 个相同大小的列表并返回它们的总和

类似

list1->val + list2->val + Sum(list1->next, list2->next)

，这与基本情况 if(list1->next == NULL) return list1->val+list2->val;

注意::我们可以轻松处理下一次传递中的进位，或者您可以在我们的 sum 函数本身中处理它

所以毕竟我们的 ans 将是 1 ->2->7->11->11->5
然后递归执行 %10 并取进位并将其添加到先前的值。

所以最终的 ans 将是 1->2->8->2->1->5

Answer 3

我会创建一个像 *head 或 *tail 这样的节点来存储我开始的节点的地址，然后迭代列表以确保我不会回到起点。这不需要计算每个的长度，这听起来效率很低。

至于递归性，只需在函数顶部进行此检查并返回 (node->value + myfunct(node->prev));如果您只做一次数学计算，那么效率会更高。

Answer 4

列表“1,2,9”和“1,3”分别代表数字“129”和“13”，在这种情况下总和是“142”。

使用递归

• 计算每个列表的长度。
• 如果长度不同，请在最短的开头用零填充。
• 递归地迭代列表，返回：a）进位数（如果有），否则为零，b）列表的尾部。

在伪代码中：

def sum_lists_rec(a, b, start_a, start_b, length_a, length_b):
    """Returns a pair of two elements: carry and the tail of the list."""

    if the end of the lists:
        return (0, empty_list)

    result = sum_lists_rec(a+1, b+1, start_a+1, start_b+1, length_a, length_b)

    carry = (a[0] + b[0] + result[0]) / 10
    digit = (a[0] + b[0] + result[0]) % 10

    return (carry, [digit] ++ result[1])

def sum_lists1(a, b):
    length_a = length(a)
    length_b = length(b)

    if length_a < length_b:
        a = [0, 0, ..., (length_b - length_a)] ++ a
    else if length_b < length_a:
        b = [0, 0, ..., (length_a - length_b)] ++ b

    result = sum_lists_rec(a, b, length_a, length_b, 0, 0)

    if result[0] != 0:
        return [result[0]] ++ result[1]
    else:
        return result[1]

作为替代方案，您可以使用堆栈：

• 计算每个列表的长度。
• 如果长度不同，请在最短的开头用零填充。
• 将两个列表的每个数字压入堆栈。
• 弹出堆栈直到为空，创建新列表。