一个c++程序，用于将两个长度不等的单链表相加，这两个链表的所有节点中都包含一个数字。

Question

我拿到这个作为面试问题。我得到了两个长度不等的链表，它们的每个节点都包含一个数字。我被要求构建一个第三个链表，它包含两个链表的和，同样是以节点中的1位数字的形式。例:链表1是4-7-9-6链表2是5-7那么第三个链表是4-8-5-3有人能给我一个有效的算法吗，在空间复杂度方面最小的折衷？(我不期望一个算法涉及多次颠倒列表)。

Answer 1

1. 反向逐个元素列出1和2
2. 和(同时保持进位)，将结果放入从尾部到头部构建的列表3中

或

1. 将列表1和2转换为整数(例如int list1AsInt = 0; For each node {list1AsInt *= 10; list1AsInt += valueOfThisNode;} )
2. 求和这些整数
3. 将结果转换为链表(例如valueOfBrandNewNode = list3AsInt % 10; list3AsInt /= 10; Add a new node that points to the prev one; )

或

1. 遍历两个列表一次，以找出它们的长度。对于这个例子，让我们假设列表1比列表3长N，列表3表示不带进位的和，列表4表示进位。
2. 对于列表1的前N个节点，将这些值复制到列表3，并使列表4的值为0。
3. 对于列表1和2的其余节点，逐个元素求和，将总和mod 10放在列表3中，并将进位放在列表4中。通过布尔值来跟踪列表4是否全为0。
4. 将值为0的最后一个节点添加到列表4中。如果列表4完全是0，则执行
5. 。否则，返回到步骤2，将列表3视为新列表1，将列表4视为新列表2。我们知道新列表1的长度是旧列表1和旧列表2的长度中较大的一个，并且新列表2的长度比旧列表1和旧列表2的长度多一。

Answer 2

对于这两个列表，

1. 将每个数字作为其ASCII码等效项读取到从0开始索引的字符数组中。
2. 在两个字符数组上使用atoi()函数(如果您关心长度，可以使用atol()或atoll() )
3. 将两个数字相加
4. 使用itoa()函数转换为字符数组，然后放回新列表。

不过，我承认itoa()函数不是标准的。

Answer 3

如果列表是双重链接的，这很容易：

1. 遍历两个列表到末尾。
2. 将数字添加到相应节点中，并保留进位数字。
3. 在列表3中创建节点。
4. 将一个节点移到列表的开始位置，然后重复。