将表示数字的链表相加

链表

在计算机科学中，链表是一种数据结构，数据以线性方式存储，但不是存储在连续的内存位置。它是一系列相互连接的节点，每个节点包含数据值和下一个值的地址。

问题陈述

在这里，我们有两个链表，我们需要将这两个链表视为两个数字进行相加，并将和以链表的形式返回。

例如

我们有两个链表，如下所示：

在上面的例子中，list1 代表数字 2342，list2 代表数字 95607。如果我们对这两个数字求和，结果将是 97949，我们将以链表的形式返回这个数字。

任何数字的最高有效数字将是链表的头，数字的最低有效数字将是链表的最后一个节点。

方法 1

解决这个问题的最直接的方法是将两个链表转换为等效的整数值，然后将这两个数字的和存储在一个整数值中。现在，我们将这个整数转换为链表。

Java 代码

输出

说明

• 在上面的代码中，我们为节点和列表实现了一个自定义类。借助自定义类，我们创建了两个链表。
• 现在，我们使用两个函数：一个函数用于获取链表的整数等效值，另一个函数用于根据给定的整数创建链表。
• 要获取链表的整数等效值，我们首先通过遍历链表来找出链表的大小。在确定节点数量（这将是数字的位数）后，我们再次遍历链表，并将值与相应的 10 的幂相加，根据它们的索引。
• 在获取两个数字的整数等效值后，我们得到它们的和，然后将这个和转换为列表。第二个函数返回链表的头。
• 在此函数中，我们使用递归方法创建列表。我们为数字的最后一位创建节点，并为其余值调用递归函数。在获得剩余值的头节点后，我们将当前节点添加到从剩余数字获得的列表的末尾。
• 对于基本情况，如果数字仍然是单数字，我们将创建节点并仅返回该节点。
• 上述代码的时间复杂度：为 **O(N)**，其中 N 是两个列表中元素的最大数量。
• 上述代码的空间复杂度：为 **O(N)**

方法 2

我们将遍历两个列表并在遍历期间添加值。

在这种方法中，我们将反转两个列表并开始添加元素。我们将维护一个进位变量，该变量将在下一次迭代中不断传播。如果最后仍有进位 1，我们将创建该进位的额外节点。否则，我们不会，因为结果链表将是反序的，所以我们将再次反转它以获得实际顺序。

Java 代码

时间复杂度： O(N)

空间复杂度： O(N)