💡 Problem Formulation: Given two singly linked lists, the objective is to find the first common element between them. For instance, if the first linked list is 1 -> 2 -> 3 -> 4 and the second is 6 -> 3 -> 4, the desired output is 3, as it is the first element that appears in both lists.
Method 1: Hash Table Approach
This approach entails traversing the first linked list and storing each element in a hash table (a set in Python). Then, we traverse the second linked list and check each element against the hash table. The first match is the first common element. This method offers O(m+n) time complexity, where m and n are the lengths of the linked lists.
Here’s an example:
class Node:
def __init__(self, value):
self.value = value
self.next = None
def common_element_hash_table(list1, list2):
seen = set()
while list1:
seen.add(list1.value)
list1 = list1.next
while list2:
if list2.value in seen:
return list2.value
list2 = list2.next
return None
# Example usage
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)
head2 = Node(6)
head2.next = Node(3)
head2.next.next = Node(4)
print(common_element_hash_table(head1, head2))
Output:
3
In this code snippet, we declare a Node class for our linked list, then define a function common_element_hash_table() that takes two linked lists. We iterate over the first list adding each element to a set, then iterate over the second list to find the first common element. Finally, we call the function with two linked lists and print the result.
Method 2: Brute Force
The brute force method involves comparing each node of the first linked list with each node of the second linked list until a common element is found. This approach has a time complexity of O(m*n), making it less efficient for long lists.
Here’s an example:
def common_element_brute_force(list1, list2):
while list1 is not None:
current = list2
while current is not None:
if list1.value == current.value:
return list1.value
current = current.next
list1 = list1.next
return None
# Example usage
# (Assuming the same Node class and linked lists from the previous example)
print(common_element_brute_force(head1, head2))
Output:
3
This function, common_element_brute_force(), straightforwardly compares each element of the first list with each element of the second list using two nested loops, returning the first common value found or None if no commonality exists.
Method 3: Two Pointers Approach
The two pointers approach is efficient when both linked lists are sorted. Pointers start at the heads of their respective lists, advancing independently until a common element is found, boasting a time complexity of O(m+n).
Here’s an example:
def common_element_two_pointers(list1, list2):
while list1 and list2:
if list1.value == list2.value:
return list1.value
elif list1.value < list2.value:
list1 = list1.next
else:
list2 = list2.next
return None
# Example usage
# (Assuming the same Node class and linked lists from the previous examples)
print(common_element_two_pointers(head1, head2))
Output:
3
The common_element_two_pointers() function uses two pointers, which move through both lists. When a common element is found, or one of the list ends, the search stops. If a common element is found, it is returned; otherwise, None is returned.
Method 4: Recursive Approach
A recursive solution relies on the call stack to compare the nodes of the two linked lists. Note that recursion may lead to a stack overflow on very large lists. This method is also O(m+n).
Here’s an example:
def common_element_recursive(list1, list2):
if list1 is None or list2 is None:
return None
if list1.value == list2.value:
return list1.value
return common_element_recursive(list1.next, list2) or common_element_recursive(list1, list2.next)
# Example usage
# (Assuming the same Node class and linked lists from the previous examples)
print(common_element_recursive(head1, head2))
Output:
3
The common_element_recursive() function works by comparing the current nodes of both lists and then moving to the next node of either one or both lists when necessary. The recursion continues until a common element is found or one list runs out of nodes.
Bonus One-Liner Method 5: Using List Comprehension with Hashing
This one-liner is a concise way to combine list comprehension with hashing. It converts one linked list to a set and then iterates over the second linked list, producing a list of common elements.
Here’s an example:
common_element_one_liner = lambda list1, list2: next((node.value for node in list2 if node.value in set(node.value for node in list1)), None) # Example usage print(common_element_one_liner(head1, head2))
Output:
3
This one-liner defines a lambda function that takes two lists. It creates a set from the first list and then uses list comprehension to search for the first element in the second list that is also in the set. It returns the first common element found, or None if there is no match.
Summary/Discussion
- Method 1: Hash Table Approach. Strengths: Efficient with O(m+n) complexity and simpler to understand. Weaknesses: Requires additional memory for the hash table.
- Method 2: Brute Force. Strengths: Simple to implement and understand. Weaknesses: Least efficient with O(m*n) complexity, not suitable for large lists.
- Method 3: Two Pointers Approach. Strengths: Efficient with sorted lists. Weaknesses: Inapplicable if lists are not sorted.
- Method 4: Recursive Approach. Strengths: Elegant recursive solution. Weaknesses: Risk of stack overflow with very large lists.
- Bonus Method 5: One-Liner with List Comprehension. Strengths: Extremely concise. Weaknesses: Potentially less readable and does not inherently work with data structures other than lists.