##### Updated on February 10, 2019

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. 😁