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

Rate this post

π‘ 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

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

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

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
```

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: Iterative Comparison. Straightforward and efficient. Handles different-sized lists well. Method 2: Recursive Comparison. Elegant, but can lead to a stack overflow for very long lists. Method 3: Convert to Python Lists and Compare. Simple to understand. Inefficient due to the need for list conversion. Method 4: Hashing. Quick to execute, but has a small chance of false positives due to hash collisions. Method 5: Using All and Zip. Concise one-liner. Requires lists to be converted to Python lists first – which may add overhead.