Identical Linked Lists

Problem

Given the two singly Linked Lists respectively. The task is to check whether two linked lists are identical or not.

Two Linked Lists are identical when they have the same data and with the same arrangement too. If both Linked Lists are identical then return true otherwise return false.

Examples:

Example 1:

Input:
LinkedList1: 1->2->3->4->5->6
LinkedList2: 99->59->42->20
Output: Not identical 

Example 2:

Input:
LinkedList1: 1->2->3->4->5
LinkedList2: 1->2->3->4->5
Output: Identical

• Expected Time Complexity: $O(n)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1 <= n <= 10^3$

Solution

Python

def areIdentical(head1, head2):
    temp1 = head1
    temp2 = head2
    while temp1 is not None and temp2 is not None:
        if temp1.data!=temp2.data:
            return False
        temp1 = temp1.next
        temp2 = temp2.next
    return True

Java

public boolean isIdentical (Node head1, Node head2){
    Node temp1 = head1;
    Node temp2 = head2;
    while (temp1!=null && temp2!=null) {
        if (temp1.data!=temp2.data)
            return false;
        temp1 = temp1.next;
        temp2 = temp2.next;
    }
    return temp1 == null && temp2 == null;
}

C++

bool areIdentical(struct Node *head1, struct Node *head2) {
    struct Node* temp1 = head1;
    struct Node* temp2 = head2;
    while (temp1 != nullptr && temp2 != nullptr) {
        if (temp1->data != temp2->data)
            return false;
        temp1 = temp1->next;
        temp2 = temp2->next;
    }
    return temp1 == nullptr && temp2 == nullptr;
}

C

bool areIdentical(struct Node *head1, struct Node *head2) {
    struct Node* temp1 = head1;
    struct Node* temp2 = head2;
    while (temp1 != NULL && temp2 != NULL) {
        if (temp1->data != temp2->data)
            return false; 
        temp1 = temp1->next;
        temp2 = temp2->next;
    }
    return temp1 == NULL && temp2 == NULL;
}

• Time Complexity: $O(n)$
• Auxiliary Space: $O(1)$