查找两个链表的交点

在此问题中，我们将给出两个链表。这两个链表将在两个链表的某个节点处合并，形成一个 Y 形链表。我们需要找到链表合并的节点。

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

输入

列表1 = 1 -> 2 -> 3 -> 4 -> 5

列表2 = 9 -> 8 -> 4 -> 5

输出 4

两个列表在两个链表的节点 4 之后合并

方法 - 1

解决此问题的最基本方法是使用嵌套循环。外层循环将遍历第一个链表的每个节点，内层 while 循环将遍历第二个链表。内层 while 循环将检查列表 2 的当前节点是否与列表 1 的当前节点相同。如果条件满足，那么我们就找到了交点。如果循环在没有找到交点的情况下结束，那么我们将返回 None。

以下是实现上述方法的 Python 程序。

代码

输出

The intersection node is: 4

时间复杂度：由于使用了嵌套循环，此程序的​​时间复杂度为 O(m * n)。这里，m 和 n 是两个链表的节点数。

空间复杂度：我们没有使用任何额外的空间，因此空间复杂度是常数。

方法 - 2

在此方法中，我们将使用不同的链表结构。我们将对基本结构进行一些修改，这将有助于我们解决此问题。我们将向链表中添加一个新的变量，该变量将存储布尔值 True 或 False。此变量将跟踪节点是否已被访问。

我们将首先遍历第一个链表，并将第一个链表的所有节点标记为已访问。然后，我们将遍历第二个链表。对于每个节点，我们将检查该节点是否已被访问。如果节点已被访问，则表示我们在第一个链表中已访问过该节点，这意味着链表在此特定节点处相交。如果我们已完成第二个链表的遍历而未遇到已被访问的节点，则表示两个链表在任何点都不相交。这种方法比以前的方法更好，因为我们不使用嵌套循环来遍历链表。我们将使用线性遍历来查找节点的交集。

代码

输出

The intersection node is: 4

我们不需要创建一个新变量。我们也可以使用哈希表。

代码

输出

The intersection node is: 4

时间复杂度：我们遍历两个链表一次。为了遍历链表，我们使用了一个线性循环。因此，遍历的时间复杂度是两个链表长度之和。因此，时间复杂度为 O(m + n)。m 和 n 是两个链表的长度。我们取总长度是因为，在最坏的情况下，链表可能没有交集，在这种情况下，将遍历完整的链表。

辅助空间：我们创建了一个列表来存储已被访问过的节点。节点将只存储一次。因此，空间复杂度将是此列表的长度。在最坏的情况下，此列表的长度将为 O( max(m, n) )，其中 max(m, n) 是两个链表中较长链表的长度。

方法 - 3

在此方法中，我们将利用两个链表的节点数量差异来找到两个链表的交点。

我们将按照以下步骤解决此问题。

• 首先，我们将计算第一个链表中存在的节点数量。
• 然后，我们将计算第二个链表中存在的节点数量。
• 然后，我们将计算两个链表节点数量之间的差值。将此差值存储为 diff。
• 现在，我们必须遍历节点数量较多的链表。我们将从第一个节点开始遍历此链表，直到到达列表的第 d 个节点。从第 d 个节点开始，两个链表都具有相同数量的节点。
• 现在，我们将运行另一个循环，以便一起遍历两个链表。我们将并行遍历列表并检查是否有任何共同节点。两个列表的第一个共同节点将是交点节点。
• 如果我们找不到任何交点，我们将返回 False。

以下是此方法的 Python 代码。

代码

输出

The intersection node is: 4

时间复杂度： O(m + n)

辅助空间： O(1)

方法 - 4

在此方法中，我们将使用哈希来查找交点。此方法与我们使用列表存储已访问节点的方法类似，不同之处在于这次我们将使用 HashSet 来存储节点。算法很简单。首先，我们将初始化一个空的哈希集。初始化后，我们将遍历第一个链表并将此链表的所有节点存储在哈希集中。在下一步中，我们将遍历第二个链表，并且对于每个节点，我们将检查该节点是否在哈希集中。如果节点在哈希集中，则表示它是交点节点，因此我们将返回该节点。如果没有交点节点，则函数将返回 False。

代码

输出

The intersection node is: 4

时间复杂度：我们使用两个线性循环，它们将一直迭代直到两个链表都被遍历；因此，程序的​​时间复杂度为 O( m + n )

辅助空间：我们使用了额外的空间来存储节点；因此，空间复杂度是线性的，即 O(n)。

方法 - 5

在此方法中，我们将使用著名的双指针方法来查找交点。以下是此方法的算法

• 首先，我们将初始化两个指针，它们将指向两个链表的头部。让这些指针为 p1 和 p2，分别指向 list1 和 list2。
• 现在，我们将初始化一个 while 循环。此 while 循环将一直运行，直到两个指针指向同一个节点。
  • 在 while 循环中，我们将两个指针分别移动到它们各自链表的下一个节点。
  • 在下一步中，我们将检查两个指针是否都指向 None。如果是这种情况，则链表没有交点。因此，我们将返回 None。
  • 如果其中任何一个指针指向 None，那么我们将将其重定向到其链表的头部节点。即，如果 p1 == None，则 p1 = list1，如果 p2 == None，则 p2 = list2。
• 经过一些迭代后，两个指针要么都指向 None，要么指向交点。因此，while 循环将终止。

代码

输出

The intersection node is: 4

时间复杂度：我们使用一个线性循环，它将一直迭代直到两个链表都被遍历；因此，程序的​​时间复杂度为 O( m + n )

辅助空间：我们没有创建任何额外的空间来存储任何东西；因此，空间复杂度是常数，即 O(1)。

方法 - 6

在此方法中，我们将使用两个堆栈来查找交点。首先，我们将初始化两个堆栈。在下一步中，我们将遍历两个链表并将它们的所有节点添加到每个堆栈中。然后，我们将初始化一个变量，该变量将存储交点。让这个变量为 merge_point = None。我们将启动一个 while 循环，该循环将一直运行，直到堆栈的顶元素不相等为止。在 while 循环内部，我们将弹出堆栈的顶元素并将该节点存储在变量 merge_point 中。当 while 循环结束时，我们将返回 merge_point，它将包含两个链表的交点。如果链表没有交点，那么 while 循环将不会执行，并且将返回 merge_point = None。

代码

输出

The intersection node is: 4

时间复杂度：我们遍历两个链表一次。为了遍历链表，我们使用了一个线性循环。因此，遍历的时间复杂度是两个链表长度之和。因此，时间复杂度为 O(m + n)。m 和 n 是两个链表的长度。在最坏的情况下，while 循环将花费 O(min(m, n))。因此，平均时间复杂度为 O(m, n)。

辅助空间：我们创建了两个堆栈来存储两个链表的节点。节点将只存储一次。因此，空间复杂度将是两个堆栈的总长度。因此，空间复杂度将为 O(m + n)。