5 Best Ways to Check Whether 2 Linked Lists are the Same in Python

💡 Problem Formulation: Checking whether two linked lists are identical is a common problem in computer science. This involves comparing the nodes of the two lists for equality in sequence and value. An input example would be two linked lists, where each contains a sequence of nodes. The desired output is a boolean value indicating whether the linked lists are identical or not.

Method 1: Iterative Comparison

The iterative comparison method involves traversing both linked lists simultaneously and comparing each pair of nodes. The function returns True if all pairs of nodes are equal until the end of both lists is reached; otherwise, it returns False.

Here’s an example:

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def are_identical(head1, head2):
    current1, current2 = head1, head2
    while current1 and current2:
        if current1.value != current2.value:
            return False
        current1, current2 = current1.next, current2.next
    return current1 is None and current2 is None

# Example linked lists
list1 = ListNode(1, ListNode(2, ListNode(3)))
list2 = ListNode(1, ListNode(2, ListNode(3)))

# Check if they are identical
print(are_identical(list1, list2))

Output:

True

This code snippet defines a ListNode class to represent each node in a linked list. The are_identical function iteratively traverses both linked lists and compares the value of each node. It returns True only if all corresponding nodes are equal in both lists and both lists have the same length.

Method 2: Recursive Comparison

In the recursive comparison method, a recursive function is used to compare nodes from both linked lists starting from the head node. If all the nodes are identical and the base case of reaching the end of both lists is met, the method returns True.

Here’s an example:

def are_identical_recursive(node1, node2):
    if node1 is None and node2 is None:
        return True
    if node1 is not None and node2 is not None and node1.value == node2.value:
        return are_identical_recursive(node1.next, node2.next)
    return False

# Example usage
print(are_identical_recursive(list1, list2))

Output:

True

This code snippet features a recursive function, are_identical_recursive, which checks if the current nodes are identical and then calls itself for the next pair of nodes. This process continues until the end of both linked lists is reached or a mismatch is found. Recursion simplifies the function and naturally handles the iterative comparison process.

Method 3: Convert to Python Lists and Compare

This method converts both linked lists to Python lists. This allows for the built-in comparison capabilities of Python lists to determine if both linked lists have the same elements in the same order.

Here’s an example:

def to_list(node):
    result = []
    current = node
    while current:
        result.append(current.value)
        current = current.next
    return result

# Convert linked lists to Python lists and compare
print(to_list(list1) == to_list(list2))

Output:

True

The to_list function converts a linked list into a Python list by iterating through the linked list and adding each node’s value to the Python list. After conversion, the straight-forward comparison of Python lists with the ‘==’ operator gives us the answer.

Method 4: Hashing

Hashing can be employed by computing a hash value for both linked lists and comparing those hashes. If the hashes are equal, the lists are potentially identical. However, this method is prone to hash collisions, so additional checks might be necessary.

Here’s an example:

import hashlib

def hash_linked_list(node):
    hash_sha = hashlib.sha256()
    current = node
    while current:
        hash_sha.update(str(current.value).encode('utf-8'))
        current = current.next
    return hash_sha.hexdigest()

# Compare hashes of two linked lists
print(hash_linked_list(list1) == hash_linked_list(list2))

Output:

True

This code snippet creates a hash for each linked list using SHA-256. It iterates through each list, updating the hash with the string representation of each node’s value. Comparing these hashes can quickly indicate if the lists are likely identical, though this is not a foolproof method due to the small chance of collisions.

Bonus One-Liner Method 5: Using All and Zip

This one-liner method uses the all function and zip within a list comprehension to check node equality across both lists in a concise expression.

Here’s an example:

identical = all(n1.value == n2.value for n1, n2 in zip(to_list(list1), to_list(list2)))
print(identical)

Output:

True

The code uses a list comprehension to iterate over pairs of nodes from both lists simultaneously using zip, checking for equality. The all function then confirms that every comparison is True. This offers a compact solution if both lists are already converted to Python lists.

Summary/Discussion

Method 1:

Method 2:

Method 3:

Method 4:

Method 5: