Check if two linked list are equal in java

Question

I am basically completing a hacker rank excercise where you return 1 if the list is completely equal meaning there are same number of nodes in two lists and all the values in nodes also equal. Otherwise you return 0.

This is the method I wrote and for some reason I keep failing the test case i am not sure why. I wrote down some test cases in my book and did hand tracing and still can't seem to figure it out why.

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;
}

Yes i found many solutions online but I am more curious as to why my solution is not working.

• CollinD: Everywhere you have equal = 0 should be return 0 I suspect.
• mastov: If your first list has only 1 element, you are never comparing that element with the first element of the second list.
• mastov: Also, it's better to use !temp.data.equals(temp2.data) instead of temp.data != temp2.data
• user1010101: @mastov I do because I do temp.data != temp2.data
• mastov: No, that check will never be executed, if you have only 1 element. Then your loop while(temp.next != null) won't execute a single time.

Answer 1

The code

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;
}

will never compare the last element of the first list with the corresponding element of the second list because your loop stops early. Try this instead:

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

Using temp != null as loop condition makes sure, we also check the last element. The same adaption has been done for the check temp2.next == null, which is now temp2 == null. And this check has to be done before the comparison of data, in order to avoid a NullPointerException during the data comparison.

I personally would write that part more like this:

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

I consider it easier to understand because it is symmetric. Usage of equals makes sure, we compare the actual content of the payload, not just references. I'd also use boolean as return type.

Answer 2

You can use recursive function.

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);
 }

Hope this will help !! :)

Answer 3

This works:

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);
}

• John3136: Congratulations on your first answer. The quality would be much better if you explained what you are doing instead of just providing a code dump.
• Khanh: This reedit from " recursive function" above. This check either headA or headB has null first. Fixed this case.

Answer 4

And the cleanest way ever:

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;
}

Answer 5

public int compare_list(Node A, Node B) {
 Node tail_A = A;
 Node tail_B = B;
 while(tail_A != null && tail_B != null){
 if(tail_A.val != tail_B.val){
 return 0;
 }
 tail_A = tail_A.next;
 tail_B = tail_B.next;
 }
 if(tail_A == tail_B){
 return 1; // if Equal lengths and same values 
 }
 else{
 return 0; // Only length are not equal
 } 
}