Identical Linked List in Java

相同的链表是指两个链表包含相同的数据且顺序也相同。要在 Java 中判断两个链表是否相同，我们可以通过迭代或递归的方式比较对应的节点。这涉及到同时检查数据和结构，直到所有节点都匹配或发现不匹配项。

示例

输入

列表1 1, 2, 3, 4

列表2 1, 2, 3, 4

输出

链表是相同的。

解释

"链表是相同的"，因为两个列表具有相同的数值序列：1、2、3 和 4。每个列表中对应的节点都具有相同的数据，并且两个列表同时结束，没有数据或结构上的不匹配。

示例 2

输入

列表1 1, 2, 3, 4

列表2 1, 2, 5, 4

输出

链表不相同。

解释

"链表不相同"，因为数据存在不匹配。虽然两个列表的前两个节点具有相同的值（1 和 2），但列表 1 的第三个节点的值是 3，而列表 2 的第三个节点的值是 5。这种不匹配使得链表不同。

方法 1：逐节点迭代比较

算法

步骤 1：初始化指针： 使用两个指针，current1 和 current2，分别指向第一个和第二个链表的头节点。

步骤 1.1： 检查空指针

在继续之前，请确保头指针（current1 或 current2）都不是 null。

如果两者都为 null，则链表相同，因为它们都是空的。如果只有一个为 null，则链表不相同，因为一个链表为空而另一个不为空。

步骤 2：遍历两个列表： 使用循环，只要 current1 和 current2 都不为 null，就遍历这两个列表。在每一步，比较 current1 和 current2 中存储的数据。

步骤 3：检查不匹配： 如果当前节点（current1.data 和 current2.data）的数据不匹配，则立即得出链表不相同的结论并退出循环。

步骤 4：移动到下一个节点： 如果数据匹配，则将两个指针（current1 和 current2）都移动到它们各自的下一个节点。

步骤 5：检查结束条件： 退出循环后，检查两个指针是否都为 null。如果两个指针都为 null，则表示两个列表具有相同的长度和结构，并且所有数据都匹配。得出链表相同的结论。如果一个指针为 null 而另一个不为 null，则链表在长度或结构上有所不同，因此不相同。

步骤 6：返回结果： 根据上述条件，如果链表相同则返回 true，否则返回 false。

文件名：IdenticalLinkedList.java

输出

 
The linked lists are identical   

复杂度分析

空间复杂度

检查两个链表是否相同的时空复杂度为 O(n)，其中 n 是较短链表的长度。这是因为算法同时遍历两个列表，直到找到不匹配项或两个列表都完全遍历完毕。

空间复杂度

检查两个链表是否相同的空间复杂度为 O(1)。这是因为算法只使用固定量的额外空间用于遍历链表的指针。没有使用其他 数据结构 或递归调用，因此在内存方面效率很高。

方法 2：使用递归逐节点比较

递归逐节点比较方法通过递归比较节点来检查两个链表是否相同。从头开始，它会验证每个节点的 数据和结构，然后继续到下一个节点，直到链表结束或出现不匹配。对于链表中清晰、分步的比较，它很有效。

算法

步骤 1：定义基本情况： 两个列表都为空：如果两个头指针（head1 和 head2）都为 null，则表示两个列表都为空。在这种情况下，链表相同，因此我们返回 true。一个列表为空，而另一个不为空

如果一个头指针为 null 而另一个不为 null，则链表的长度或结构不同。在这种情况下，我们返回 false，因为链表不相同。

步骤 2：比较当前节点： 如果两个头指针都不为 null，则比较当前节点（head1.data 和 head2.data）的数据值。如果数据值不相等，则表示链表不相同，因此返回 false。如果数据值匹配，则继续比较两个列表中的下一个节点。

步骤 2.1：处理数据不匹配： 如果当前节点（head1.data 和 head2.data）的数据不匹配，则链表不相同。在这种情况下，立即返回 false，而不继续处理后续节点。这可以确保算法在找到不匹配项时立即停止，从而节省不必要的比较。

步骤 3：递归检查剩余节点： 在两个列表的下一个节点（head1.next 和 head2.next）上调用相同的 函数。此递归调用的结果决定了链表的其余部分是否相同。如果在任何时候发生不匹配，该函数将返回 false。

步骤 3.1：递归调用逻辑： 要检查剩余的节点，请使用两个列表的下一个节点（head1.next 和 head2.next）调用相同的函数。这会继续比较链表的其余部分。如果递归调用返回 true，则表示剩余节点相同。否则，立即返回 false。

步骤 4：返回结果： 如果函数成功达到两个指针都为 null 的基本情况，则表示所有节点都匹配，链表相同。如果在过程中出现任何比较失败，则函数返回 false。

步骤 5：输出结果： 递归函数完成后，使用其返回值显示结果。如果函数返回 true，则打印链表相同。否则，打印链表不相同。此步骤总结了用户或调用程序的比较结果。

文件名：IdenticalLinkedListRecursive.java

输出

 
The linked lists are identical   

复杂度分析

时间复杂度

此递归算法的时空复杂度为 O(n)，其中 n 是较短链表的长度。这是因为算法遍历两个链表中的每个节点恰好一次，比较对应的节点，直到到达链表末尾或找到不匹配项。

空间复杂度

递归算法的空间复杂度为 O(n)，这是由于调用堆栈。每次递归调用都会向堆栈添加一个帧，该帧与链表中的节点数量成比例。对于大型列表，与迭代方法相比，这可能会导致 内存 使用量增加。