Identical Linked Lists

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Check if two linked lists are identical (same values in same order).

Algorithm

1Traverse both simultaneously. If values differ or lengths differ: false. If both reach null: true.

Common Pitfalls

•Simple O(n) comparison. Same as LC 100 but for linked lists.

Identical Linked Lists.java

Java

// Approach: Traverse both lists simultaneously, comparing each node's data. Both must end at the same time.
// Time: O(n) Space: O(1)

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class Solution {
    // Function to check whether two linked lists are identical or not.
    public boolean areIdentical(Node head1, Node head2) {
        while (head1 != null && head2 != null) {
            if (head1.data != head2.data)
                return false;

            head1 = head1.next;
            head2 = head2.next;
        }

        if (head1 == null && head2 == null)
            return true;

        return false;
    }
}

Was this solution helpful?