Intersection of two lists in Python

Why this matters

Two linked lists can join at one node and continue as a single chain. The part after the join is shared. Both lists point to the same node objects from that point on. The task is to find the first shared node.

This comes up when two lists hold different items but lead into the same records. For example, a list of order lines and a list of refunds might both point to the same customer record at the end. Finding the join point is also a clean way to practise two ideas from earlier lessons: moving a reference along a chain, and comparing references instead of values. The earlier lessons in this module on singly linked lists cover the basics this lesson depends on. The palindrome check in the next lesson of this module uses the same moves.

Same value is not the same node

A node is one object of the ListNode class. It has a val attribute and a next attribute. An attribute is a named piece of data stored on an object. A reference is a name that points to an object. Two references are the same when they point to the same object.

Python has two ways to compare things, and this difference decides the whole lesson.

• a is b checks whether both names point to the same object.
• a.val == b.val checks whether both nodes hold the same number.

ListNode does not define its own ==, so a == b on two nodes also checks identity. The lesson uses is anyway, because it says what the code means, and a class cannot change what is does.

Here is a simple case. Build two lists, each holding 1 and then 2:

C:  1 -> 2 -> None
D:  1 -> 2 -> None

The values match, but the four nodes are different objects. The first 1 in C is not the first 1 in D. Two separate calls to build always create new nodes. So C and D have no shared node, even though they look the same when printed.

Now look at a list pair that does share nodes. In the picture below, the node with value 8 is one object. Both lists point to it.

A:  4 -> 1 -----\
                  >  8 -> 4 -> 5 -> None
B:  5 -> 6 -> 7 -----/

A has two nodes before the shared part, 4 and 1. B has three nodes before it, 5, 6 and 7. The shared part is 8, 4, 5. Notice that the value 4 appears in A's first node and again inside the shared part. Those are two different nodes. Only the shared part is the same object.

The goal is to return the first shared node, here the node with value 8. If the lists share nothing, the answer is None.

Two words will help in the rest of the lesson:

• The prefix is the part of a list before the shared part. A has prefix length 2. B has prefix length 3.
• The tail is the shared part, which runs to the end of both lists. Here the tail has length 3.

The lists in the picture have total lengths of 5 and 6. Length means the number of nodes.

Idea 1: the length-difference method

Think of two people walking the same road toward the same finish line. One started 1 kilometre further back. If the faster person waits until the gap is closed, both reach each point at the same time after that. The same idea works here.

The method has three steps.

1. Count the nodes in each list. A has 5 nodes and B has 6.
2. Move the head of the longer list forward by the difference. The difference is 6 minus 5, which is 1. So B's pointer moves one node forward, from 5 to 6.
3. Walk both pointers forward one node at a time, until they are the same object. Return that node.

Step 2 works because, after the move, both pointers have the same number of nodes left before the end of their lists. The shared part is at the end of both lists, so both pointers reach it at the same step. The first pair of equal pointers is the first shared node.

Let us follow the example by hand.

• Start: pointer a is at 4, pointer b is at 5.
• Step 2 moved b forward by 1, so b is at 6.
• Now a is 2 nodes from the shared 8, and b is also 2 nodes from 8. In a, that is 4 then 1 then 8. In b, that is 6 then 7 then 8.
• Move both once: a is at 1, b is at 7. They are not equal.
• Move both once more: a is at 8, b is at 8. They are the same object, so the answer is 8.

Here is the full program. It uses a small ListNode class and five helpers. build makes a new list from numbers. join attaches an existing list to the end of a new prefix. This is how the shared tail is created in the program. value_of returns the val of a node, or None when the node is None, so the output can be printed safely.

The output from one run was this. Your output will be the same, because the program uses no random numbers and no timing.

A = 4 -> 1 -> 8 -> 4 -> 5 -> None
B = 5 -> 6 -> 7 -> 8 -> 4 -> 5 -> None
length_difference: 8
two_pointers:      8
C = 1 -> 2 -> None
D = 1 -> 2 -> None
length_difference: None
two_pointers:      None

The first two results show the node 8 for both methods. The last two show None for the separate lists, which is correct because they share no node.

The length-difference method makes three passes over the lists. It first counts, then aligns, then walks. For a beginner, the three passes are easy to follow. The cost is about the total of both lengths, which is fine for a practice problem.

Idea 2: the two-pointer switch

The second method needs no counting. Its trick is to let each pointer walk both lists.

Pointer pa starts at the head of A. Pointer pb starts at the head of B. Each step moves both one node forward. When a pointer falls off the end and becomes None, it jumps to the head of the other list on the next step. Then it keeps going. The loop stops when the two pointers are the same object, or when both are None.

The Python code is short:

def two_pointers(a, b):
    pa = a
    pb = b
    while pa is not pb:
        pa = b if pa is None else pa.next
        pb = a if pb is None else pb.next
    return pa

The expression b if pa is None else pa.next means: if pa is None, set it to b, the head of B. Otherwise move it to pa.next. The same rule works for pb with a. This form is called a conditional expression. It is the Python version of cond ? x : y.

Here is the trace for A = 4 -> 1 -> 8 -> 4 -> 5 and B = 5 -> 6 -> 7 -> 8 -> 4 -> 5. Each line shows both pointers after one step. None means the pointer just fell off its list.

start: pa=4 pb=5
step 1: pa=1 pb=6
step 2: pa=8 pb=7
step 3: pa=4 pb=8
step 4: pa=5 pb=4
step 5: pa=None pb=5
step 6: pa=5 pb=None
step 7: pa=6 pb=4
step 8: pa=7 pb=1
step 9: pa=8 pb=8
meet at value 8

Read the trace in order. At step 5, pa fell off the end of A, so it is None. At step 6, it jumped to the head of B, which is 5. At step 6, pb fell off the end of B and became None. At step 7 it jumped to the head of A, which is 4. By step 9, both pointers stand on the node 8.

The trace looks odd at first. Each pointer walks its own list and then the other list. Both pointers walk the same total number of nodes, and both walks run through the shared tail at the end. That is the key fact in the next section.

Note the difference between the two methods. The length-difference method needs the lengths first. The two-pointer method does not. It walks a little more than the total length of both lists, but in one pass.

Why both pointers meet

A proof is a short argument that something must happen every time. Here we want to show that the two-pointer method always stops on the first shared node, or on None when there is no shared node. Use three counts:

• p is the number of nodes in the prefix of A.
• q is the number of nodes in the prefix of B.
• s is the number of nodes in the shared tail.

For the example, p is 2, q is 3 and s is 3. The lengths are p + s for A and q + s for B. That is 5 and 6.

Follow pointer pa and count its moves. It walks the p prefix nodes of A and then the s shared nodes. It reaches the first shared node after p moves. Then it walks on through the rest of the tail to None, which takes s more moves, so p + s moves in all. A move from the last node to None counts as one move. The switch to the head of B is one more move. So pa is at the head of B after p + s + 1 moves. From there it still has q prefix nodes of B to walk, and then it reaches the first shared node. That happens after p + s + 1 + q moves in total.

Follow pointer pb the same way. It walks the q prefix nodes of B and the s shared nodes, then None, then the switch to the head of A. It is at the head of A after q + s + 1 moves. It needs p more moves to reach the first shared node. So it arrives there after q + s + 1 + p moves in total.

Both numbers are p + q + s + 1. The two pointers arrive at the first shared node after the same number of moves.

For the example, that number is 2 + 3 + 3 + 1, which is 9. The trace above shows both pointers at 8 at step 9. The count matches.

The pointers cannot meet earlier on a node that is not shared. A node in the prefix of A belongs only to A. The loop can only make both pointers equal when they stand on one object, and only a shared node is an object that both lists reach. The first shared node is the first one either pointer can reach in common, so the first match is the first shared node.

There is one special case. If p equals q, both pointers reach the first shared node on the same step before the switch even happens. The first match is still the first shared node. Both pointers were at the same distance from the join, so they arrive together.

Now the case with no shared node. Here s is 0. Each pointer walks its whole list, then None, then the other list. Both pointers become None at some step. When that happens, pa and pb are the same object, both None, so the loop stops and returns None. For lists of the same length, they become None at the same step and the loop stops at once. For lists of different lengths, they become None at different steps, and the loop continues until both are None at the same step, after at most the sum of the two lengths plus one move. The loop always ends, so there is no infinite walk.

The length-difference method has its own short proof. After alignment, both pointers have the same number of nodes left. If the lists share a tail, both lists end at the same node, so a node counted from the end is the same object in both lists exactly when it is in the tail. Walking the pointers together, the first match is therefore the first node of the tail. If the lists share nothing, no pair of nodes matches, and both pointers reach None at the same time.

Worked example 2: the join is at the head of one list

The first example had the join in the middle of both lists. Here the join is at the very start of B. This case shows that the answer can be the head of a list.

Take A = 9 -> 4 -> 7 -> 2 -> None and B = 7 -> 2 -> None. The node 7 in B is the same object as the third node of A. So the intersection is the node 7, which is B's head.

Length-difference method:

• lengths are 4 for A and 2 for B.
• The difference is 2, so A's pointer moves two nodes forward. It is now at 7.
• B's pointer is at 7 already. They are the same object, so the answer is 7 at once.

Two-pointer method: the program below gives the answer 7 for both methods. The code is the same as before, with a new input.

seven = build(7, 2)
a = join(build(9, 4), seven)
b = seven
print(value_of(length_difference(a, b)))   # prints 7
print(value_of(two_pointers(a, b)))        # prints 7

This is worth noticing. A common mistake is to assume the answer must be a node inside both lists in the middle. The answer is just the first node that both lists reach, and that can be a head.

Worked example 3: a pair that does not match

Now a pair with equal values and no shared node. Build 1 -> 2 and then build a second 1 -> 2 from new nodes. The two lists look the same when printed. The program gives None for both methods, which is correct. The lengths are both 2, so both pointers become None on the same step, and the loop stops.

The key point is that the algorithm never looks at values. It only compares object identity, which is what is does on two names. If you change the example so that one list is 1 -> 2 and the other is 5, the answer is still None, and the loop still stops because both pointers become None eventually.

Common mistakes

The first mistake is comparing values instead of nodes. A value check looks plausible, and it passes simple tests, but it returns the wrong node when the values repeat. Here is a function that does that:

def by_value(a, b):
    x = a
    while x is not None:
        y = b
        while y is not None:
            if x.val == y.val:
                return x
            y = y.next
        x = x.next
    return None

On the example lists A = 4 -> 1 -> 8 -> 4 -> 5 and B = 5 -> 6 -> 7 -> 8 -> 4 -> 5, it returns the node with value 4. The first node of A has value 4, and B also has a 4. That node is not shared. The correct answer is the node with value 8. On these lists, the two functions return different nodes:

shared = build(8, 4, 5)
a = join(build(4, 1), shared)
b = join(build(5, 6, 7), shared)
print("by_value:", value_of(by_value(a, b)))
print("two_pointers:", value_of(two_pointers(a, b)))

by_value: 4
two_pointers: 8

The second mistake is walking off the end without a None check. In the two-pointer method, a pointer that is None cannot ask for .next. If you write pa = pa.next without the check, Python raises an error when pa is None:

def no_null_check(a, b):
    pa = a
    pb = b
    while pa is not pb:
        pa = pa.next
        pb = pb.next
    return pa
 
 
no_null_check(build(1, 2), build(5))

The call uses the lists 1 -> 2 and 5. The last line of the error from one run was:

AttributeError: 'NoneType' object has no attribute 'next'

The message says that None has no next attribute, so reading .next from it fails. The fix is the conditional that jumps to the other head when the pointer is None.

The third mistake is skipping the alignment step in the length-difference method. The walk then starts with both pointers at their own heads, so they are not the same distance from the join. Here is the bad version:

def no_alignment(a, b):
    while a is not b:
        a = a.next
        b = b.next
    return a
 
 
shared = build(8, 4, 5)
a = join(build(4, 1), shared)
b = join(build(5, 6, 7), shared)
no_alignment(a, b)

On the example lists, a falls off its end after 5 moves, while b is still on a node. The next move reads .next from None, and the error is the same kind as before:

AttributeError: 'NoneType' object has no attribute 'next'

Without alignment, the walk meets at the join only when both lists have the same length. The alignment step is what makes the two walks meet at the join.

The fourth mistake is ending the loop too early. Some people write while pa is not None and pb is not None. This stops as soon as either pointer falls off its list. In the example, pa falls off after 5 steps while pb is still on a node. The loop stops at that point and returns None, even though 8 is shared. The loop must keep going until the two pointers are the same object, including when they are both None.

Practice

Exercise 1. Let A be 1 -> 2 -> 3 -> 9 -> 10 -> None and B be 7 -> 9 -> 10 -> None. The nodes 9 and 10 are shared. Use the length-difference method. Give the two lengths, the difference, and the node returned.

Show the answer

The length of A is 5 and the length of B is 3. The difference is 2, so A's pointer moves two nodes forward. It goes from 1 to 2 to 3. Now both pointers are one node from the join. Walk both one step at a time. A moves to 9 and B moves to 9. They are the same object, so the method returns the node 9.

Exercise 2. Let A be 2 -> 6 -> 8 -> None and B be 5 -> 8 -> None. The node 8 is shared. Use the two-pointer method. Write each step, the value of each pointer, and the step where they meet. Check your answer against the proof: the prefix of A has length 2, the prefix of B has length 1, and the shared tail has length 1.

Show the answer

Step 1: pa is at 6 and pb is at 8. Step 2: pa is at 8 and pb is at None. Step 3: pa is at None and pb jumps to the head of A, which is 2. Step 4: pa jumps to the head of B, which is 5, and pb moves to 6. Step 5: pa moves to 8 and pb moves to 8. They meet on the node 8 after 5 steps. The proof gives p + q + s + 1, which is 2 + 1 + 1 + 1, or 5. The two numbers agree.

Exercise 3. Here is a broken version of the two-pointer loop:

def broken(a, b):
    pa = a
    pb = b
    while pa is not None and pb is not None and pa is not pb:
        pa = pa.next
        pb = pb.next
    return pa if pa is pb else None

Run it on A = 4 -> 1 -> 8 -> 4 -> 5 and B = 5 -> 6 -> 7 -> 8 -> 4 -> 5. What does it return, and why?

Show the answer

It returns None. The loop stops after 5 steps, because pa falls off the end of A at that point, while pb is still on the node with value 5. The loop never switches the pointers to the other lists, so it never reaches the shared node. The fix is to remove the None tests from the loop condition and do the switch inside the loop, as in the lesson.

Exercise 4. Let A be 9 -> 4 -> 7 -> 2 -> None and B be 7 -> 2 -> None, where B's head is the node 7 from A. What does each method return? Explain why the answer is not a node in the middle of either list.

Show the answer

Both methods return the node 7. The length of A is 4 and the length of B is 2. The length-difference method moves A's pointer two nodes forward, which lands on the node 7. B's pointer is already on the node 7, so the two are the same object at once. The answer is the first node both lists reach, and here that is the head of B. A join can be at any position, including the head of one list.

Summary

• Two references are the same when they point to the same object. Compare references with is, not values with .val.
• The length-difference method counts both lists, moves the longer head forward by the difference, then walks both pointers together.
• The two-pointer method walks each list and then the other list, so both pointers take the same total number of moves to reach the shared tail.
• Both pointers reach the first shared node after the same number of moves, which the proof gives as the prefix of A plus the prefix of B plus the tail plus one.
• If the lists share nothing, both methods return None. The loop must continue until both pointers are the same object, including when both are None.