Python解决方案：获取双向链表中给定和的数对

在这个问题中，我们给定一个双向链表和一个正整数。我们必须找到值加起来等于给定数字的节点对。此问题的一个约束是，我们必须以恒定的空间复杂度解决它。

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

示例

输入: head = 2 ó 3 ó 6 ó 4 ó 5 ó 1 ó 7 ó 9 ó 8 ó 0, x = 10

输出 (6, 4), (9, 1), (8, 2), (3, 7)

方法 - 1

解决此问题的基本方法是遍历链表。在每次迭代中，使用另一个循环来遍历剩余的链表。在每次内部循环迭代中，检查节点值是否加到 x。如果是，则将节点对存储在列表中。最后，我们将返回对的列表。

代码

输出

The pairs are [[2, 8], [1, 9], [3, 7], [6, 4]]

时间复杂度: 我们使用了非线性循环来遍历链表。这两个循环的时间复杂度都是 O(n)。因此，最终的时间复杂度将是 O(n) * O(n)，等于 O(n ^ 2)。

空间复杂度: 我们使用了额外的空间来存储对。除此之外，我们没有使用任何额外的空间；因此，此算法的空间复杂度是恒定的，即 O(1)。

方法 - 2

有一个比之前的方法好得多的方法。我们将使用双指针技术来查找和等于 x 的节点对。我们现在将讨论该问题的算法。

我们将在程序开始时初始化两个指针。一个指针将指向给定双向链表开头处的节点，即链表的头节点。第二个指针将指向链表末尾的节点。我们将运行一个循环，使第二个指针指向链表的最后一个节点。

然后，我们将启动一个 while 循环。当两个指针交叉时，while 循环将结束。如果从链表头部开始，第一个指针在最后一个指针的后面。

在每次迭代中，我们将检查当前指针节点的总和是否等于 x。如果是，我们将打印该特定对。

在此之后，我们将第一个指针向前移动，并将最后一个指针向后移动。

如果我们遇到两个指针都指向同一个节点的情况，则表示不存在这样的对，因此我们将打印结果。

下面是上述针对此问题的优化方法的 Python 代码。

代码

输出

( 8 , 2 )
( 3 , 7 )
( 9 , 1 )

时间复杂度: 我们使用线性循环来遍历链表；因此，时间复杂度是线性的，即 O(n)

辅助空间: 我们没有使用任何额外的空间；因此，空间复杂度是恒定的，即 O(1)。