Problem in checking if 2 Linked Lists are containing same values in java

Question

I was asked to write a method that runs on a Linked List and checks if 2 of the lists contain the same values (It doesn't have to be the same order of values between them both).

Here's my code:

    public boolean Equals(Object obj) {
    if(obj instanceof LinkedList) //Checks if the object it got is a Linked List
    {
        if(this.length() != ((LinkedList)obj).length())
            return false;
        Node head1 = head;
        Node head2 = ((LinkedList) obj).getHead();
        boolean ans = false;
        this.toString();
        ((LinkedList)obj).toString();
        while(head1 != null)// Running on the 1st list values
        {
            while(head2 != null) { // comparing each value in the 2nd list to see if it's on the 1st list as well
                if(head2.getValue() == head1.getValue())
                    ans = true;
                head2 = head2.getNext();
            }
            if(ans == false)
                return false;
            ans = false;
            head1 = head1.getNext();
        }
        return true;
    }
    else
        return false;
}

I'm adding also the structure's class that you wouldn't have any difficulties on understanding:

public class LinkedList {

// Attributes

private Node head, tail;
private int length;

// Constructor

public LinkedList() {

    head = tail = null;
    length = 0;
}

// getHead

public Node getHead() {

    return head;
}

// getTail

public Node getTail() {

    return tail;
}

// Length

public int length() {

    return length;
}

// isEmpty

public boolean isEmpty() {

    return head == null;
}

It returns false on all the cases no matter what, I don't manage to enter my error, thanks a lot!!

In case you would like to see the other way for that https://stackoverflow.com/a/2762137/10867487 — Echoinacup, Jan 08 '19 at 19:08
What's the return type of `Node::getValue`? Is it a reference type, that you should be comparing with `equals` instead of `==`? Or is it primitive? Also, you don't seem to reset `head2` when the outer loop restarts. — Dawood ibn Kareem, Jan 08 '19 at 19:08
It is primitive and the return type is int, and the problem was that i wasn't reseting head2 in the end of the outer loop, thank you very much I'm greatful!!! — weaver20, Jan 08 '19 at 19:12
I think the solution is still not right, even with the reset. Would would happen if `obj` contained some elements that `this` doesn't? — Dawood ibn Kareem, Jan 08 '19 at 19:23
I don’t think that it’s a real problem since if obj is not an instance of LinkedList then it will immediately return false — weaver20, Jan 09 '19 at 11:10
One solution with O(n) time and O(n) space complexity is to use HashMap and Key as linkedlist's node value and value as count of that, iterate another list and reduce counts, at the end if all keys have value 0 => both lists have same values else not — dkb, Jan 10 '19 at 09:30

score 0 · Answer 1 · answered Jan 10 '19 at 05:51

Your solution wouldn't work , if the lists are of type -

list A : 1 -> 1 -> 1
list B : 1 -> 2 -> 3

because in 2nd while loop , ans will set to true , because it will match 1 to 1.

to solve your problem - you need to sort both lists and then compare.

Or you can use hashing to compare if both lists are equal.

Problem in checking if 2 Linked Lists are containing same values in java

1 Answers1