# 5 Best Ways to Find Intersection of Two Linked Lists in Python

Rate this post

π‘ Problem Formulation: Imagine you have two singly linked lists that might intersect at some point and become a single list. The intersection point means the two lists share all the nodes after the intersection node, not merely having two nodes with the same value. The goal is to find the node where the intersection begins. Given linked lists A and B, the output should be the reference of the intersected node or `null` if there is no intersection.

## Method 1: Brute Force Approach

The brute force method involves traversing the first linked list and for each node, traversing the entire second linked list to check for the same node. This method’s function specification would involve nested iterations over both lists, comparing nodes by their addresses until a match is found or returning `null` if no intersection exists.

Here’s an example:

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

while currentB is not None:
currentB = currentB.next
return None

# Example usage
# Assuming we have two linked lists that intersect at some node.
```

The output of this code snippet would be the reference to the intersection node if one exists or `null` if there is no intersection.

This method directly compares nodes one by one, which is easy to understand but inefficient with a time complexity of O(M*N) where M and N are the lengths of the two linked lists.

## Method 2: Hash Table

Using a hash table, we store nodes of the first linked list and then check each node of the second linked list for existence in the hash table. If a node is found, it’s the intersection. If we reach the end of the second list without finding any node in the hash table, there is no intersection.

Here’s an example:

```def getIntersectionNode_hash(headA, headB):
nodes = set()
return None

```

The output will be the intersection node or `null`.

This snippet uses a set to hash visited nodes, avoiding nested loops. This reduces complexity to O(M+N). However, it requires additional space O(N) for the hash table.

## Method 3: Two Pointer Technique

In the two pointer technique, pointers for both lists traverse the nodes sequentially. When they reach the end of a list, they continue from the beginning of the other list. If an intersection exists, the pointers will meet at the intersection node.

Here’s an example:

```def getIntersectionNode_two_pointers(headA, headB):
return None
while pointerA != pointerB:
pointerA = pointerA.next if pointerA else headB
pointerB = pointerB.next if pointerB else headA
return pointerA

# Example usage assumes heads of the two lists are known.
```

The output will be the intersection node or `null`.

This method ensures that both pointers traverse equal lengths by switching lists. It is efficient with time complexity O(M+N) and does not require extra space.

## Method 4: Difference of Node Counts

First, count the nodes in both lists. Calculate the difference in counts, and then advance the pointer of the longer list by the difference. Now, traverse through both lists in tandem to find the intersection point.

Here’s an example:

```def getIntersectionNode_diff_counts(headA, headB):
def count_nodes(node):
count = 0
while node:
count += 1
node = node.next
return count
for _ in range(abs(countA - countB)):
long = long.next
while long and short and long != short:
long, short = long.next, short.next
return long

# Example usage assumes the heads of the two lists are given.
```

The output will be the reference to the intersection node.

This method finds the intersection by negating the length difference. It has a time complexity of O(M+N) but executes with no additional space, which makes it space efficient.

## Bonus One-Liner Method 5: Set Symmetric Difference

Although Python does not support pointer operations as in C and C++, for the sake of a thought exercise, one can simulate a similar concept using sets and their symmetric difference operation. This is not a practical method but an interesting one-liner approach.

Here’s an example:

```# Assuming we have node objects for both linked lists
intersection_node = list(set(nodesA) ^ set(nodesB))[-1] if set(nodesA) & set(nodesB) else None
```

The output will be the reference to the intersection node if it exists; otherwise, it returns `null`.

This one-liner attempts to find the intersection using set operations, which is not practical due to the inability to create such sets of nodes in pure Python.

## Summary/Discussion

Method 1: Brute Force Approach. Benefits from simplicity, but suffers from high time complexity O(M*N). Not recommended for large lists.
Method 2: Hash Table. Improved time efficiency O(M+N) but requires extra memory O(N) for the hash table. Good for moderate-length lists.
Method 3: Two Pointer Technique. Optimal for time complexity O(M+N) and does not use extra space. Best for most practical scenarios.
Method 4: Difference of Node Counts. Also time-efficient O(M+N) and uses no extra space, providing a different algorithmic approach to the same problem.
Method 5: Set Symmetric Difference. A theoretical approach not applicable to Python lists, illustrating the need to understand language capabilities when solving problems.