检查 java 中的两个链表是否相等

Question

我基本上是在完成一个黑客等级练习，你 return 1 如果列表完全相等意味着两个列表中的节点数相同并且节点中的所有值也相等。否则你 return 0.

这是我写的方法，出于某种原因，我一直无法通过测试用例，我不确定为什么。我在我的书中写下了一些测试用例并进行了手描，但似乎仍然无法弄清楚为什么。

int CompareLists(Node headA, Node headB) {
    // This is a "method-only" submission. 
    // You only need to complete this method 
    Node temp = headA;
    Node temp2 = headB;
    int equal = 1;

    if(temp == null && temp2 == null){
        equal = 1;
    }
    else if((temp == null && temp2 != null) || (temp!=null && temp2 == null)){
        equal = 0;
    }
    else{
    while(temp.next != null){
        if(temp.data != temp2.data || temp2.next == null){
            equal = 0;
            break;
        }
        temp = temp.next;
        temp2 = temp2.next;
    }
    if(temp2.next != null){
        equal = 0;
    }
    }

  return equal;
}

是的，我在网上找到了很多解决方案，但我更好奇为什么我的解决方案不起作用。

Answer 1

密码

while(temp.next != null){
    if(temp.data != temp2.data || temp2.next == null){
        equal = 0;
        break;
    }
    temp = temp.next;
    temp2 = temp2.next;
}
if(temp2.next != null){
    equal = 0;
}

永远不会将第一个列表的最后一个元素与第二个列表的相应元素进行比较，因为您的循环提前停止。试试这个：

while(temp != null){
    if(temp2 == null || temp.data != temp2.data){
        equal = 0;
        break;
    }
    temp = temp.next;
    temp2 = temp2.next;
}
if(temp2 != null){
    equal = 0;
}

使用temp != null作为循环条件确保，我们也检查最后一个元素。对检查 temp2.next == null 进行了相同的调整，现在是 temp2 == null。并且此检查必须在之前 data 的比较，以避免 data 比较期间的 NullPointerException。

我个人会更像这样写那部分：

while(temp != null && temp2 != null){
    if(temp.data.equals(temp2.data)){
        return false;
    }
    temp = temp.next;
    temp2 = temp2.next;
}
return temp == temp2;

我认为它更容易理解，因为它是对称的。使用 equals 确保我们比较有效负载的实际 content，而不仅仅是引用。我也会使用 boolean 作为 return 类型。

Answer 2

你可以使用递归函数。

public boolean isIdenticalRecursive(Node a, Node b) {
        if (a == null && b == null) {
            return true;
        }

        if (a.data != b.data)
            return false;
        return isIdenticalRecursive(a.next, b.next);
    }

希望这会有所帮助！！ :)

Answer 3

这个有效：

int CompareLists(Node headA, Node headB) {

    if ((headA == null)^(headB == null))
        return false;

    if ((headA == null) && (headB == null))
        return true;

    if (headA.data != headB.data) 
        return false;
    return CompareLists(headA.next, headB.next);
}

Answer 4

有史以来最干净的方式：

static boolean compareLists(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    while(head1 != null && head2 != null && head1.data == head2.data) {
        head1 = head1.next;
        head2 = head2.next;
    }

    return head1 == head2;
}

检查 java 中的两个链表是否相等

Check if two linked list are equal in java

java

linked-list