在C中有效地添加两个链表

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

我正在考虑使用stack解决问题。我将遍历两个列表并将数据元素推送到两个单独的堆栈中。每个链接列表。然后我将两个堆栈一起弹出并添加两个元素，如果结果是两位数字没有I 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; 

我在面试问题中多次遇到过这个问题，但这是我能想到的最好的解决方案。 如果有人能在ci中找到更高效的东西，那将非常高兴。

Answer 1

两次传球，没有筹码：

• 获取两个列表的长度。

• 使用一个节点创建解决方案列表。 将此节点的值初始化为零。 这将保持进位数。 将列表指针（称为进位指针）设置为此节点的位置。 将列表指针（称为结束指针）设置为此节点的位置。

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

• 现在我们留下两个列表指针，每个列表指针具有相同数量的节点。

• 虽然列表不是空的……

  • 将新节点链接到结束指针并将结束指针前进到此节点。

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

  • 将两个值一起添加。

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

    2. 如果值为9。 设置它。 什么都不做。

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

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

Answer 2

这就是我要解决这个问题的方法：

第1步：在两个链接列表上传递，查找长度

说len(L1) = m and len(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. 时间复杂度的第2步： O(n) ，运行时堆栈空间
2. 时间复杂度的第3步： O(d) ，运行时堆栈空间

总计： O(n + d) OR O(n)

Answer 3

我只是分别找到每个链表的总值，将它们加在一起，然后将该数字转换为新的链表。 因此，将4-> 7-> 9-> 6和5-> 7分别转换为值为4796和57的整数。 将它们一起添加到4853，然后将其转换为包含4-> 8-> 5-> 3的链表。 您可以使用简单的数学运算进行转换。

如果您改变数字首先表示的方式，那么按照自己的方式进行操作会容易得多。 这样，数字总是第一位，然后是十位数，接着是数百位，等等。

编辑：因为你显然使用了大量的数字：你有没有考虑过制作双链表？ 那么你本身就不需要逆转它了。 只是向后移动它。

Answer 4

使用堆栈并不比反转列表更有效（实际上它正在反转列表）。 如果您的堆栈对象是动态分配的，这没什么大不了的，但如果您使用调用递归创建它，您将很容易获得错误排序的堆栈溢出 。 🙂

Answer 5

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