Overlapping linked lists

Given two linked list nodes, one might overlap the other. That is, one linked list might contain a sequence that is already in the other linked list. The two linked lists share a common node.

Problem

Build a function that takes two singly linked lists and returns a boolean output that signifies whether or not the two linked lists share a common node.

Input

• ll_a : linked list A
• ll_b : linked list B

Examples:

LinkedList 0 : A -> B -> C -> D

LinkedList 1 : Z -> X -> A -> B -> C -> D

LinkedList 0 and LinkedList 1 share some common nodes, in particular, A, B, C, and D.

LinkedList 2 : E -> F -> G

LinkedList 3 : H -> I -> J

LinkedList 2 and LinkedList 3 do not share common nodes.

Approach

The easiest strategy is to use \(O(n)\) space. We can use a boolean dictionary that has keys representing each linked list node in ll_a or ll_b (one or the other is the most efficient). For this demonstration, I will choose ll_a.

Next, we iterate through each node in ll_a and record its existence in the boolean dictionary.

After that, we iterate through each node in ll_b and check it against our dictionary. If we come across a key that already has the True value associated with it, then we know there is an overlap.

Solution

def does_overlap(ll_a, ll_b):  
    exists = collections.defaultdict(bool)

    while ll_a:
        exists[ll_a] = True  # assumes that linked list nodes can be represented uniquely as a key string
        ll_a = ll_a.next

    while ll_b:
        if exists[ll_b]:
            return True
        ll_b = ll_b.next

    return False

This algorithm uses \(O(n)\) space and \(O(n)\) time.

Solution (Optimized)

We can optimize this algorithm by making the key observation that if the two linked lists do share a node, then they must have the same tail node.

Going back to the example at the top of the page:

LinkedList 0 : A -> B -> C -> D

LinkedList 1 : Z -> X -> A -> B -> C -> D

We see that both linked lists have the same tail node D.

This means that as long as we have two pointers pointing to the start of the shared linked list (in this example, that would be A), we can simply iterate both of the pointers (moving forward one node at a time) and compare the two pointers each time. If the pointers are equal, we have detected an overlap.

We can achieve this by counting the number of nodes in ll_a and ll_b, and getting the absolute difference of the two, i.e. |count(ll_a) - count(ll_b)|.

Once we have the difference (call it \(x\)), we can move the head pointer of the larger linked list forward by \(x\) times.

The rest becomes simple. We now have two pointers in ll_a and ll_b pointing to the earliest position where the start of the shared linked list could be (if it even exists). We keep traversing these two pointers in tandem until we come across an equivalent match with each other, which implies that the two lists share this node.

def does_overlap_fast(ll_a, ll_b):

    def count(llist):
        c = 0
        while llist:
            llist = llist.next
            c += 1
        return c

    ll_a_count = count(ll_a)
    ll_b_count = count(ll_b)  # assume ll_b is greater in size
    diff = abs(ll_a_count - ll_b_count)

    # if ll_a is actually greater, then swap linked lists so that ll_b is greater as assumed above
    if ll_a_count > ll_b_count: 
        ll_a, ll_b = ll_b, ll_a

    for _ in range(diff):  # move forward by offset on the larger linked list
        ll_b = ll_b.next

    while ll_a and ll_b:  # since ll_b is moved by offset, these two ptrs will reach null at the same time
        if ll_a == ll_b:
            return True
        ll_a = ll_a.next
        ll_b = ll_b.next

    return False

This algorithm uses \(O(1)\) space and \(O(n)\) time. 😁