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

💡 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

def getIntersectionNode_bruteforce(headA, headB):
    while headA is not None:
        currentB = headB
        while currentB is not None:
            if currentB == headA:
                return headA
            currentB = currentB.next
        headA = headA.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()
    while headA is not None:
        nodes.add(headA)
        headA = headA.next
    while headB is not None:
        if headB in nodes:
            return headB
        headB = headB.next
    return None

# Example usage assumes that headA and headB are the heads of the two linked lists.

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):
    if headA is None or headB is None:
        return None
    pointerA = headA
    pointerB = headB
    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
    countA, countB = count_nodes(headA), count_nodes(headB)
    long, short = (headA, headB) if countA > countB else (headB, headA)
    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.