Java 中两个链表的交点

在一个系统中，给定了两个单向链表。由于某种错误，其中一个链表的最后一个节点连接到了第二个链表。这样就创建了一个 Y 形链表。我们的任务是找出给定的两个链表合并的点。

根据上图，115 是两个链表的交点。

方法/算法：使用两个循环

使用两个嵌套的 for 循环，我们可以找到解决方案。外层循环用于遍历第一个链表，内层循环用于遍历第二个链表。对于外层循环的每次迭代，完整地遍历第二个链表，并检查外层循环指向的节点是否存在于内层循环遍历的链表中。

实施

观察上述方法的实现。

文件名： LinkedListIntersection.java

输出

The first linked list is: 
113 116 119 115 130 
The second linked list is: 
110 115 130 
The first intersection point of the linked lists is: 115

复杂度分析： 上述程序的 time complexity 为 O(m * n)，其中 m 是第一个链表中节点的总数，n 是第二个链表中节点的总数。由于程序没有使用任何额外的空间，因此 space complexity 为 O(1)。

方法：使用节点计数

步骤 1： 计算第一个链表中存在的节点数，在我们的例子中为 c1。

步骤 2： 计算第二个链表中存在的节点数，在我们的例子中为 c2。

步骤 3： 计算 c1 和 c2 之间的差值，并将其存储在变量 diff 中。

步骤 4： 从 I = 0 开始循环到 diff，然后开始遍历第一个链表的节点，直到达到 diff 值。

步骤 5： 现在开始并行遍历两个链表。当我们找到共同节点时，返回其值。如果达到 null，则可以返回 -1，表示两个链表没有交点。

实施

观察上述算法的实现。

文件名： LinkedListIntersection.java

输出

The first linked list is: 
113 116 119 115 130 
The second linked list is: 
110 115 130 
The first intersection point of the linked lists is: 115

复杂度分析： 上述程序的 time complexity 为 O(m + n)，其中 m 是第一个链表中节点的总数，n 是第二个链表中节点的总数。由于程序没有使用任何额外的空间，因此 space complexity 为 O(1)。

方法：使用 HashSet

步骤 1： 创建一个 HashSet 用于存储整数。

步骤 2： 开始一个循环遍历第一个链表。将第一个链表中的所有节点存储在第一步创建的 HashSet 中。

步骤 3： 开始一个循环遍历第二个链表。在每次遍历时，检查该遍历指向的节点的值是否存在于 HashSet 中。如果存在，立即终止循环并返回该值。如果循环遍历完成，则意味着链表的交点不存在。

实施

观察上述算法的实现。

文件名： LinkedListIntersection.java

输出

The first linked list is: 
113 116 119 115 130 
The second linked list is: 
110 115 130 
The first intersection point of the linked lists is: 115

复杂度分析： 程序的 time complexity 与上述相同。程序的 space complexity 为 O(m)，m 是第一个链表中节点的总数。这是因为我们使用了一个哈希集来存储第一个链表中节点的值。

方法：使用两个指针

步骤 1： 将两个指针 p1 和 p2 初始化在 h1 和 h2。

步骤 2： 一次一个节点地遍历链表。

步骤 3： 当 p1 到达链表的末尾时，将其重定向到 h2。

步骤 4： 同样，当 p2 到达链表的末尾时，将其重定向到 h1。

步骤 5： 一旦两个链表都经过重定向，它们将与碰撞点保持相同的距离。

步骤 6： 如果在任何节点 pt1 与 p2 重合，则表示该节点是交点节点。

步骤 7： 第二次迭代后，如果没有交点节点，则返回 NULL。

实施

观察上述算法的实现。

文件名： LinkedListIntersection2.java

输出

The first linked list is: 
113 116 119 115 130 
The second linked list is: 
110 115 130 
The first intersection point of the linked lists is: 115

复杂度分析： 程序的 time complexity 与上述相同。程序的 space complexity 为 O(1)，因为程序不使用任何额外的空间。

方法：创建循环的第一个链表

步骤 1： 开始一个循环遍历第一个链表。一直走到第一个链表的最后一个节点。在遍历过程中，计算链表中节点的数量，并将其存储在一个变量中，即 countNode。同时，将链表的最后一个节点存储在一个变量中。

步骤 2： 现在，将链表的最后一个节点连接到链表的第一个节点。这样，就创建了一个循环链表（链表中的循环）。

步骤 3： 由于第一个链表的长度已知，使用指针 p2 遍历第二个链表，遍历的节点数等于第一个链表的长度。

步骤 4： 从第二个链表的头部 (h2) 开始另一个指针。

步骤 5： 使用循环，一次移动 h2 和 p2 一个节点。循环的终止条件应为 (p2 != h2)。当 p2 和 h2 相遇时，该点就是给定两个链表的第一个交点。

步骤 6： 将第一个链表的最后一个节点指向 null。这样，第一个链表就通过移除链表中的循环恢复了其原始状态。

实施

观察上述算法的实现。

文件名： LinkedListIntersection3.java

输出

The first linked list is: 
113 116 119 115 130 
The second linked list is: 
110 115 130 
The first intersection point of the linked lists is: 115

复杂度分析： 程序的复杂度分析与上述相同。

方法：使用数学方程

步骤 1： 开始一个循环遍历第一个链表，以计算节点数。将计数存储在一个变量中，即 s1。

步骤 2： 开始一个循环遍历第二个链表，以计算节点数。将计数存储在一个变量中，即 s2。同时，将链表的最后一个节点存储在一个变量中，即 l1。

步骤 3： 现在，使用循环反转第一个链表。

步骤 4： 开始一个循环遍历第二个链表，以计算节点数。将计数存储在一个变量中，即 s3。同时，将链表的最后一个节点存储在一个变量中，即 l2。

步骤 5： 比较存储在 l2 和 l1 中的地址。如果它们相同，则两个链表不相交。如果它们不同，则转到下一步。

步骤 6： 链表公共节点总数为 (s1 + s2 - s3) / 2。将此值存储在一个变量中，即 y。

步骤 7： 现在，在第二个链表中遍历 (s2 - y) 个节点。指针的当前位置就是两个链表的交点。

步骤 8： 再次反转第一个链表以恢复更改。

实施

观察上述算法的实现。

文件名： LinkedListIntersection3.java

输出

The first linked list is: 
113 116 119 115 130 
The second linked list is: 
110 115 130 
The first intersection point of the linked lists is: 115

复杂度分析： 程序的复杂度分析与上述相同。