c - 一个 c 程序，用于添加两个不等长的单链表，在它们的所有节点中包含一个数字

Question

我得到了这个作为面试问题。我得到了 2 个长度不等的链表，每个节点都包含一个数字。我被要求建立一个第三个链表，它包含两个链表的总和，同样以节点中的 1 位数字的形式。
前任:
链表 1 是
4-7-9-6
链表 2 是
5-7
那么第三个链表将是
4-8-5-3
有人可以向我建议一种有效的算法，在空间复杂性方面的妥协最小吗？(我不希望算法数据涉及多次反转列表)。

Answer 1

反转列表 1 和 2

逐个元素求和(而
保持携带)，把
结果在列表 3，你
从尾部到头部构建

或者

将列表 1 和 2 转换为整数(例如 int list1AsInt = 0; For each node {list1AsInt *= 10; list1AsInt += valueOfThisNode;} )

将这些整数相加

将结果转换为链表(例如 valueOfBrandNewNode = list3AsInt % 10; list3AsInt /= 10; Add a new node that points to the prev one; )

或者

遍历两个列表一次以找出
他们的长度。对于这个例子，
让我们假设列表 1 更长
通过 N 个节点。

创建一个列表 3 来表示总和
没有携带和 list 4 到
代表携带。

对于列表 1 的前 N ​​个节点，
将这些值复制到列表 3 并制作
列表 4 的值为 0。

对于列表 1 的其余节点
和 2，逐个元素求和，
将总和 mod 10 放在列表 3 中，并且
进位 list 4. 跟踪通过
列表 4 是否全为 0 的 bool 值。

将最后一个值为 0 的节点添加到列表中
4.

如果列表 4 完全为 0，则完成。
否则，递归到第 2 步，
将列表 3 视为
新列表 1 和列表 4 作为新
列表 2. 我们知道长度
新列表 1 是长度中较大的一个
旧列表 1 和 2，以及长度
新列表 2 的数量比这多一个。