在C语言中高效地添加两个链表

Question

我有两个链接列表，按从最高有效位到最低有效位的顺序表示十进制数的数字。例如，4->7->9->6 和 5->7。答案应该是4->8->5->3，而不需要翻转列表，因为翻转列表会导致效率降低。

我考虑使用堆栈来解决这个问题。我将遍历这两个列表，并将数据元素分别推入两个单独的堆栈中。一个用于每个链接列表。然后，我一起弹出两个堆栈，并添加两个元素。如果结果是两位数，则对10取模并将进位存储在临时变量中。余数存储在节点中，并将进位添加到下一个总和中，以此类推。如果两个堆栈是s1和s2，结果链接列表是res。

temp = 0;
res = (node*)(malloc(sizeof(node*));

while(s1->top!=-1 || s2->top!=-1)
{  
    temp = 0;
    sum = pop(s1) + pop(s2);
    n1 = (node*)(malloc(sizeof(node*));
    temp = sum/10;
    sum = sum%10;
    sum = sum+temp;
    n1->data = sum;
    n1->next = res;
    res = n1;
    free n1;
    //temp=0;
}

if((s1->top==-1)&&(s2->top==-1))
{
    return res;
}
else if(s1->top==-1)
{
    while(s2->top!=-1)
    {
        temp = 0;
        sum = pop(s2);
        sum = sum + temp;
        temp = sum/10;
        sum = sum%10;
        n1 = (node*)(malloc(sizeof(node*));
        n1->data = sum;
        n1->next = res;
        res = n1;
        free n1;
    }
}
else
{
    while(s2->top!=-1)
    {
        temp = 0;
        sum = pop(s2);
        sum = sum+temp;
        temp = sum/10;
        sum = sum%10;
        n1=(node*)(malloc(sizeof(node*));
        n1->data = sum;
        n1->next = res;
        res = n1;
        free n1;
    }
}

return res; 

在面试问题中，我经常遇到这个问题，但这是我能想到的最佳解决方案。如果有人能用C语言提出更有效的解决方案，我将非常高兴。

- Poulami

---

你的问题标题有误导性。我看到你有一个方法，但实际问题是什么？如何把 (4->7->9->6) + (5->7) 转化成 4->8->5->3？ - Dylan

@Dylan: 一开始读起来不太明显（我需要推算一下才能理解），但这些列表代表一个数字的各个位，因此 4796 + 57 == 4853。 - Michael Burr

@Michael Burr 我并没有反转列表，我只是把数字推到一个栈里！ - Poulami

这些列表是单向链表（仅具有前向指针）还是双向链表（也具有后向指针）？ - Dylan

我已经编辑了你的问题，以澄清这些列表代表十进制数。 - R.. GitHub STOP HELPING ICE

Answer 1

无需使用栈的两次遍历:

• 获取这两个列表的长度。

• 创建一个解决方案列表并添加一个节点。将该节点的值初始化为零。 这将保存进位数字。 将一个列表指针（称其为进位指针）设置为此节点的位置。 将一个列表指针（称其为结尾指针）设置为此节点的位置。

• 从较长的列表开始，对于每个多余的节点，将新节点链接到结尾指针，并赋予其多余节点的值。 将结尾指针设置为此新节点。 如果值小于9，则将进位指针设置为新节点。

• 现在我们的两个列表指针都有相同数量的节点。

• 当列表不为空时...

• 将一个新节点链接到结尾指针，并将结尾指针前移至此节点。

• 从每个列表中获取值，并将每个列表指针前移至下一个节点。

• 将这两个值相加。

  1. 如果值大于9，则将该值设置为 value mod 10，将进位指针节点中保存的值增加1，并将进位指针移动到下一个节点。如果进位指针的值为九，则将其设置为零并跳转到下一个节点。

  2. 如果值为九。将其设置。不做其他任何操作。

  3. 如果值小于9，请将其设置。将进位指针设置为当前节点。

• 当你完成这两个列表时，请检查解决方案指针节点的值是否为零。 如果是，则将解决方案指针设置为下一个节点，删除不需要的额外数字。

- unpythonic

Answer 2

这是我解决这个问题的方法： 步骤1：遍历两个链表，找到它们的长度。

假设 L1 的长度为 m，L2 的长度为 n。 步骤2：计算两个链表长度的差异。

if ( m > n )
    d = m - n
else if ( n > m )
    d = n - m
else
    d = 0

步骤3: 将临时指针d移到较长的列表之前。 步骤4: 现在我们有两个链表需要递归相加，它们的长度相同，因此需要维护进位。 步骤5: (注意: 如果(d == 0)，则不执行此步骤)

完成步骤4后，我们得到了部分输出列表，现在需要将较长列表的剩余部分放在输出列表的开头。

if ( d > 0 )
    -Travel larger list till d positions recursively
    -Append sum = value_at_end + carry (update carry if sum >= 10) to output list at beginning
    -Repeat until difference is consumed

注意: 我解决问题是按照给我的要求，而不是建议更改底层数据结构。

时间复杂度：

1. 遍历两个链表以找到它们的长度: O(m+n)
2. 递归地对相等长度的两个链表求和 (m - d 和 n) : O(n), 假设 m > n
3. 将较长链表剩余部分附加到输出链表: O(d)

总计: O( (m+n) + (n) + (d) ) 或者 O(m+n)

空间复杂度：

1. 第二步时间复杂度: O(n), 运行时堆栈空间
2. 第三步时间复杂度: O(d), 运行时堆栈空间

总计: O(n + d) 或者 O(n)

- Rajendra Uppal

Answer 3

我会先分别计算每一个链接列表的总数值，将它们相加，再把这个数字转化成一个新的链接列表。所以要将4->7->9->6和5->7转换为整数，其值分别为4796和57。把它们相加得到4853，然后将它转换成一个链接列表，包含4->8->5->3。你可以用简单的数学运算来完成这些转换。

如果你改变数字表示方式，把个位数放在前面，十位数放在后面，百位数等等，那么按照你的方法就会容易很多。

另外，如果你使用的是大量数字，考虑使用双向链接列表，这样就不需要反转了，只需要倒序遍历即可。

- Coeffect

---

但是，如果这两个数字非常大，会发生什么？你会把它们存储在哪里？ - Poulami

这个不可行。如果 OP 的数字是链表，那么目的肯定是为了处理太大而无法适应固定大小数值类型的数字。 - R.. GitHub STOP HELPING ICE

“large” 的意思是超出 long 类型的容量？ - Dylan

但我不打算那样做！我的数字是以相反的方向表示的！ - Poulami

@Dylan 是的，"large" 意味着比 "long int" 还要大。 - Poulami

@Poulami，你考虑过将它们变成双向链表吗？这样你就可以在保持顺序的同时向后遍历它们了。 - Coeffect

Answer 4

使用堆栈并不比反转列表更有效（实际上它是在反转列表）。如果您的堆栈对象是动态分配的，这没什么大不了的，但如果您使用调用递归创建它，很容易出现糟糕的栈溢出。 :-)

- R.. GitHub STOP HELPING ICE

Answer 5

如果您使用双向链表，您可以将数字相加并使用后向链接找出要放置进位值的位置。 http://en.wikipedia.org/wiki/Doubly_linked_list

- dcpomero

---

+1 这是最佳解决方案。更好的是，您可以使用第一个数字的“prev”指针指向最后一个（使其成为循环），以便您可以在 O(1) 时间内找到结尾。 - R.. GitHub STOP HELPING ICE