Python中将链表表示的两个数字相加

在此问题中，给定两个数字。这两个数字分别写在链表的每个节点中。因此，我们得到两个表示这两个数字的链表。我们的任务是相加这两个数字并找到它们的和。我们必须以链表的形式返回它们的和。

让我们看一个例子来理解这个问题

输入

输入1：4 → 8 → 1

输入2：3 → 8 → 9

输出

8 → 7 → 0

第一个数字是 481，第二个数字是 389。输出将是 481 + 389 = 870

输入

输入1：9 → 9 → 9 → 9 → 9

输入2：1

输出

1 → 0 → 0 → 0 → 0 → 0

第一个数字是 99999，第二个数字是 1。输出将是 99999 + 1 = 100000

方法 - 1

这是一个直接的方法。我们将使用循环遍历链表并到达链表的末尾。我们将通过在节点较少的链表开头添加值为 0 的节点，使两个链表的长度相等。然后，我们将使用递归函数来求和。此递归函数将接收节点，相加值并返回进位。

这是此方法的算法。

• 我们将首先使两个链表的长度相等。我们将遍历列表直到末尾，然后在节点较少的列表开头添加值为 0 的节点。
• 我们将定义一个递归函数并将头节点传递给此函数。此函数将使用回溯来返回节点相加的进位。
• 将一个具有相加值的节点添加到输出链表中。
• 我们将返回输出链表。

以下是此方法的 Python 代码。

代码

输出

The first linked list is:
6 3 2 9
The second linked list is:
3 8 9
The resultant linked list is:
6 7 1 8  

方法 - 2

在此问题中，我们有两个链表。让我们举一个例子来理解这种方法。第一个链表是 4 → 8 → 1。这个数字是 481。我们可以使用单位和数字的数学概念从链表中提取数字。我们可以将数字乘以 10 ^ n，其中 n 是数字的位值。将所有这些位值相加后，我们将得到所需的数字。以这种方式，我们将从第二个链表 3 → 8 → 9 中提取数字，即 389。我们将相加这两个数字，得到和 870。然后，最后我们将创建一个包含和的链表，并返回这个最终的链表，它将是 8 → 7 → 0。

代码

输出

The first linked list is:
6 3 2 9
The second linked list is:
3 8 9
The resultant linked list is:
6 7 1 8  

时间复杂度：此方法的时​​间复杂度是线性的。我们仅使用一个循环遍历链表一次。因此，最终时间复杂度为 O(m + n)，其中 m 和 n 是各个链表中的节点数。

辅助空间：我们创建了一个结果链表，它将占用 O(m + n) 的内存。

方法 - 3

在此方法中，我们将使用堆栈数据结构来相加两个链表。我们将使用堆栈存储链表的节点，然后稍后使用这些堆栈将前两个堆栈节点值的和填充到第三个堆栈中。这是此方法的算法。

• 我们将从初始化三个堆栈开始：s1、s2 和 s3。
• 我们首先将节点添加到这些堆栈中。第一个链表的节点将添加到 s1，第二个链表的节点将添加到 s2。
• 我们将遍历这两个堆栈并相加节点值。我们还将跟踪要与节点值一起添加的进位项。然后，我们将在每次迭代中为当前和值创建一个新节点，并将该节点添加到 s3。
• 最后，我们将使用第三个堆栈的节点创建一个链表。链表将被反转，其中头节点代表个位数字。因此，我们将反转链表，得到和。
• 我们将返回这个最终的链表。

代码

输出

The first linked list is:
6 3 2 9
The second linked list is:
3 8 9
The resultant linked list is:
6 7 1 8  

时间复杂度： O(n)，其中 n 是较大列表的长度。

辅助空间： O(n)，额外的空间用于存储堆栈的元素。

方法 - 4

在此方法中，我们将通过遍历节点数较多的链表来相加链表。我们将首先计算两个链表的长度。然后，我们将比较长度并遍历长度比另一个链表长的链表。我们将遍历这个链表，直到两个链表的长度相同。现在，我们将同时遍历两个链表直到末尾。为了相加节点，我们将使用回溯来处理进位项。这样，最后，我们将得到包含相加节点的链表的头节点。以下是此方法的 Python 代码。

代码

输出

The first linked list is:
6 3 2 9
The second linked list is:
3 8 9
The resultant linked list is:
6 7 1 8  

方法 - 5

在此方法中，我们将通过反转两个链表来相加它们，而无需添加零。然后，我们将继续相加节点并创建一个用于相加结果的节点。最终，我们将得到最终链表的头节点。

以下是此方法的 Python 程序。

代码

输出

The first linked list is:
6 3 2 9
The second linked list is:
3 8 9
The resultant linked list is:
6 7 1 8