Question

Write an algorithm to check equality of two link lists.(java)

Answer 1

1. Start iterating from the head node of the two linked list.

2. Compare the data part of the nodes of the two linked list.

3. If matched, move to the next node of the two linked list else return false.

4. Repeat step 2 and 3 until either of the linked list points to null.

5. If both the linked list points to null then return true otherwise return false.

IMPLEMENTATION

    /* Returns true if linked lists a and b are identical, 
       otherwise false */
    boolean areIdentical(LinkedList listb) 
    { 
        Node a = this.head, b = listb.head; 
        while (a != null && b != null) 
        { 
            if (a.data != b.data) 
                return false; 
  
            /* If we reach here, then a and b are not null 
               and their data is same, so move to next nodes 
               in both lists */
            a = a.next; 
            b = b.next; 
        } 
  
        // If linked lists are identical, then 'a' and 'b' must 
        // be null at this point. 
        return (a == null && b == null); 
    }