Intersection of two lists

Why this matters

Two lists can join at one point and then continue as a single path. Picture two train lines that run separately, then merge at a station and share the track to the end. Each line has its own first stops, but the stops after the merge are the same stops. The question is: which station is the first shared one?

This comes up in real code. Two chains of records may end at the same record, and a cache may keep two lists that point at the same entry. The question also comes up in interviews, because it tests whether you think about pointers and not only about values.

This lesson assumes you know what a node and a pointer are, and how to walk a singly linked list one node at a time. Lesson 1 of this module covers those basics. Here we use them on a harder question.

The problem in plain words

A singly linked list is a chain of nodes. Each node holds a value and a pointer to the next node. A pointer is an address in memory, so a pointer to a node tells you where that node is. The last node points to nullptr, which is C++ for "no node here".

You are given two singly linked lists, A and B. Each list is known only by its head pointer, the address of its first node. Return the first node that belongs to both lists. If the lists share no node, return nullptr.

The word "shared" has a precise meaning. Two nodes are shared only when they are the same node in memory. Two nodes with the same value are not shared. Two separate nodes that both hold the value 7 are different nodes, even though their values match. This difference causes the most wrong answers, and the mistakes section comes back to it.

Here is a small example. List A holds 1, 2, 7, 8, 9. List B holds 4, 7, 8, 9. The nodes that hold 7, 8 and 9 are the same nodes in both lists. We call them the shared tail, the part at the end that both lists contain. The answer is the node holding 7, because it is the first node of the shared tail.

A:  1 -> 2 -> [7] -> 8 -> 9 -> null
                 ^
B:  4 ----------+

The bracketed node is the answer. The shape looks like the letter Y. The two arms are the private parts of each list, and the stem is the shared tail.

A first idea and why it is slow

The simplest method checks every node of A against every node of B. For each node in A, walk all of B and see whether any node has the same address. If you find one, return it.

This works, but it is slow. If A has n nodes and B has m nodes, the walk over B can repeat once for each node of A. That is about n * m steps. For two lists of 10,000 nodes, that is 100,000,000 steps.

A better idea uses a hash set, a collection that remembers which items it has seen and checks membership quickly. Store the address of every node of A in a hash set, then walk B and check each address against the set. This takes about n + m steps, but it needs memory for the set, which grows with the size of A.

The two methods in this lesson take a number of steps that grows with n + m, and they need only a few pointer variables. For the 10,000-node case, that is about 20,000 steps.

Method 1: the length difference

Here is the idea in one sentence. If the lists have different lengths, first move the start of the longer list forward until both lists have the same number of nodes left. Then walk both lists together, one node at a time. The first time the two pointers point at the same node, you have found the shared tail.

Why does this work? A shared tail has the same nodes after its first node in both lists. If both pointers have the same number of nodes left to walk, they reach the first shared node on the same step. If the lists differ in length, they would reach it on different steps, so the alignment step fixes that.

Let us trace the example. List A has 5 nodes: 1, 2, 7, 8, 9. List B has 4 nodes: 4, 7, 8, 9. The difference is 5 minus 4, which is 1. So we move the pointer for A forward by 1, to node 2. Now both pointers have 4 nodes left.

The two pointers meet on the shared 7 after one step. That is the answer.

Here is the code. It uses the Node struct and the helper functions from the full program below.

struct Node {
    int value;
    Node* next = nullptr;
};
 
int length(const Node* head) {
    int count = 0;
    for (const Node* p = head; p != nullptr; p = p->next) {
        ++count;
    }
    return count;
}
 
Node* advance(Node* p, int steps) {
    while (steps-- > 0) {
        p = p->next;
    }
    return p;
}
 
Node* intersectionByLength(Node* a, Node* b) {
    int la = length(a);
    int lb = length(b);
    if (la > lb) {
        a = advance(a, la - lb);
    } else {
        b = advance(b, lb - la);
    }
    while (a != b) {
        a = a->next;
        b = b->next;
    }
    return a;
}

Read the last loop carefully. It stops when a and b hold the same address. If there is no shared node, both pointers keep moving until both are nullptr. Both reach the end on the same step, because the lists now have equal length. Two nullptr values are equal, so the loop stops and returns nullptr. You do not need a separate check for "no intersection".

The method walks each list once to count it, walks the longer list once to align, and walks both once to compare. That is a few passes over the two lists, so the total still grows with n + m. It uses only a few integer and pointer variables.

Method 2: the two-pointer switch

The length method needs passes to count nodes. The switch method avoids counting. It uses two pointers and a rule: when a pointer reaches the end of its list, it jumps to the start of the other list. The pointers keep walking until they are equal.

Pointer pa starts at the head of A. Pointer pb starts at the head of B. On each step, move pa to the next node. If pa is already nullptr, move it to the head of B instead. Do the same for pb, with the heads swapped. Stop when pa and pb are equal.

Let us trace the same example. I give the shared nodes names: S1 for the 7, S2 for the 8 and S3 for the 9. Then list A is 1, 2, S1, S2, S3, and list B is 4, S1, S2, S3. Each row below shows the two pointers after that many steps.

At step 7 both pointers stand on S1, the first shared node. The row for step 5 is where each pointer jumped to the other list.

Here is the code. It is shorter than the length method because it has no counting and no alignment.

Node* intersectionBySwitch(Node* a, Node* b) {
    Node* pa = a;
    Node* pb = b;
    while (pa != pb) {
        pa = pa ? pa->next : b;
        pb = pb ? pb->next : a;
    }
    return pa;
}

The expression pa ? pa->next : b means: if pa is not nullptr, move to pa->next. Otherwise move to b, the head of the other list. In C++, a pointer that is nullptr counts as false in a condition, which is why the test works without writing pa != nullptr.

Why the two-pointer switch always meets

This part is the proof. It shows that the pointers do meet when a shared tail exists, and that they do not meet at a wrong node.

Split each list into two parts. Let list A have a private part with a nodes, then a shared tail C with c nodes. Let list B have a private part with b nodes, then the same tail C. When the lists have no shared tail, c is 0.

Count the moves of pointer pa. In its first pass it walks the a private nodes of A, then the c nodes of C. After a + c moves it is on nullptr. On the next move it jumps to the head of B, then walks the b private nodes of B. It reaches the first node of C after a + c + 1 + b moves.

Pointer pb does the same count with the roles swapped. It reaches the first node of C after b + c + 1 + a moves. Both numbers are equal: a + b + c + 1. So both pointers stand on the first node of C on the same move. The trace above has a equal to 2, b equal to 1 and c equal to 3, which gives 2 + 1 + 3 + 1, or 7 moves, and the table shows the meeting at row 7.

Could the pointers meet earlier, on a different node? A node in the private part of A belongs only to A, so pb never visits it. The same holds for the private part of B. The only nodes both pointers can visit are the nodes of C. So the first meeting must be on C, or both pointers must be nullptr together.

Could they meet on C before the move a + b + c + 1? Look at when each pointer first enters C. Pointer pa enters at move a, and pointer pb enters at move b. If a and b differ, one pointer is ahead of the other by that difference while both are inside C. Both move one node per step, so the gap stays the same and is not zero. Two pointers that are a fixed, nonzero distance apart inside the same list never stand on the same node. So they cannot meet during the first pass. The first time both can stand on the same node is after each has finished its first pass and come back into C from the other list, which is the move we already counted.

The case with no shared tail is simpler. When c is 0, pa reaches nullptr after a moves, then walks the b private nodes of B, and reaches nullptr again after a + b + 1 moves. pb reaches nullptr again after the same number of moves. Both are nullptr at the same move, so the loop stops with nullptr as the answer.

To check the formula on a larger case, I ran a program with a equal to 4, b equal to 2 and c equal to 3. The formula gives 4 + 2 + 3 + 1, which is 10. The loop ran 10 moves before the pointers met, and the node they met on held the value 50, the first node of the shared tail.

The full program

Here is a complete program. It builds several pairs of lists, runs both methods and prints the results. The nodes are stored in a std::vector of std::unique_ptr, so every node is freed when the program ends. The lists hold only raw pointers, which do not own the nodes. This gives a simple way to share nodes without writing your own cleanup code.

The output is:

A: lengths 5, B: 4
length method:  node with value 7
switch method:  node with value 7
same values, separate nodes: none / none
B is the tail of A: node with value 7 / node with value 7
disjoint: none / none
empty: none / none

The third line shows the value trap. List c holds three new nodes with the values 7, 8 and 9, which match the shared tail of a by value only. Both methods correctly report no intersection.

The fourth line uses a list d whose private part is 5 and 6, followed by the shared nodes. Method 1 counts 3 nodes in shared and 5 in d, moves d forward by 2, and lands on the head of shared, so the pointers match at once. Method 2 needs 6 moves, which is the formula with a equal to 0, b equal to 2 and c equal to 3.

Common mistakes

Comparing values instead of nodes. A check such as a->value == b->value finds a match between any two nodes with the same number. In the output above, the separate copy of 7 would be reported as a shared node. Always compare the pointers with a == b, which compares the addresses in memory.

Forgetting to align the longer list. If you walk both pointers from the heads without the length step, they may never stand on the shared part at the same time. Take the case where list A has 2 nodes, all of them shared, and list B has 5 nodes, 2 of them shared. Walking both from their heads at the same speed, the pointer for A reaches the end of its list while the pointer for B is still on its private nodes, so the two pointers never stand on the same shared node. A loop that stops at the end of either list reports no intersection, even though the lists share a node.

Dereferencing a null pointer. The step pa = pa->next is only safe when pa is not nullptr. Here is a version that skips the check.

Node* intersectionBuggy(Node* a, Node* b) {
    Node* pa = a;
    Node* pb = b;
    while (pa != pb) {
        pa = pa->next;
        pb = pb->next;
    }
    return pa;
}

With two lists that share no node, the pointers reach the end and then call ->next on nullptr. I compiled this with g++ -std=c++20 -Wall -Wextra -fsanitize=address and ran it with list 1, 2 and list 9. The first lines of the real output were:

AddressSanitizer:DEADLYSIGNAL
==172113==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008
==172113==The signal is caused by a READ memory access.
==172113==Hint: address points to the zero page.
    #0 0x646bb1381cab in intersectionBuggy(Node*, Node*) bug_null.cpp:88

The sanitizer is a tool that checks memory accesses while the program runs. SEGV means the program tried to read memory it does not own. The address 0x8 is a small offset from nullptr, which is the zero page, the memory at address zero. The line bug_null.cpp:88 points at pb = pb->next. List B is shorter, so its pointer reaches nullptr first. The fix is the pa ? pa->next : b form shown earlier. The process ID and the addresses in the message will be different on your machine.

Changing the lists. Neither method changes any next pointer, so they are safe to call on lists you still need. A common mistake is to set next pointers while searching, for example to mark visited nodes. That breaks the lists for the next caller.

Writing a node that contains a whole node. Beginners sometimes write a struct with a field of its own type, like this:

struct Node {
    int value;
    Node next;
};

I compiled it with g++ -std=c++20 -Wall -Wextra and got this real error:

bug_incomplete.cpp:3:10: error: field 'next' has incomplete type 'Node'
    3 |     Node next;
      |          ^~~~
bug_incomplete.cpp:1:8: note: definition of 'struct Node' is not complete until the closing brace

A Node cannot hold a whole Node inside itself, because its size would have to be larger than itself. A link is a pointer, written Node* next, which holds only an address and has a fixed size.

Practice

Exercise 1. List A holds 3, 5, 8. List B holds 6, 8, and its 8 is the same node as the 8 in A. Find the shared node. Then trace the two-pointer switch method, one row per step, until the pointers meet.

Show the answer

The shared node is the 8. Call it S. List A is 3, 5, S and list B is 6, S.

The pointers meet on S after 5 moves. The formula gives the same answer: a is 2, b is 1 and c is 1, so 2 + 1 + 1 + 1 is 5.

Exercise 2. Use the formula from the proof. List A has 4 private nodes, list B has 1 private node, and the shared tail has 2 nodes. How many moves does the two-pointer switch method make before the pointers meet?

Show the answer

The formula is a + b + c + 1, which is 4 + 1 + 2 + 1, so the answer is 8 moves.

Exercise 3. Two lists have no shared nodes. Explain why intersectionByLength does not need a special check for this case, and say what it returns.

Show the answer

After the alignment step, both pointers have the same number of nodes left. Both reach nullptr on the same step. The loop test a != b is then false, because two null pointers are equal, so the loop stops. The function returns nullptr, which means "no shared node".

Exercise 4. Write a function int sharedCount(Node* a, Node* b) that returns the number of nodes the two lists share. Use intersectionBySwitch to find the first shared node, then count the nodes from that node to the end. Return 0 when there is no shared node.

Show the answer

int sharedCount(Node* a, Node* b) {
    Node* start = intersectionBySwitch(a, b);
    int count = 0;
    for (Node* p = start; p != nullptr; p = p->next) {
        ++count;
    }
    return count;
}

When there is no shared node, start is nullptr, the loop body never runs, and the function returns 0. When the lists share the tail 7, 8, 9, the function returns 3.

Exercise 5. List A has 2 nodes and list B has 5 nodes. Both lists end with the same 2 nodes. Explain what the length method does during alignment, and why the loop then stops on the first comparison.

Show the answer

List A is entirely shared, so its head is the first shared node. List B has 3 private nodes followed by the 2 shared nodes. The difference is 5 minus 2, which is 3. The method moves the pointer for B forward by 3 nodes. That lands on the first shared node of B, the same node the pointer for A starts on. The two pointers are equal before the loop runs its first step, so the loop does not move, and the function returns the head of A.

Summary

• Two lists share a node only when the two pointers hold the same address. Equal values are not enough.
• The length-difference method skips the extra nodes of the longer list, then walks both lists together until the pointers match.
• The two-pointer switch walks each list and then the other. Both pointers reach the first shared node after a + b + c + 1 moves, where a, b and c are the sizes of the two private parts and the shared tail.
• Both methods use a fixed amount of extra memory, and neither changes the lists.
• When there is no shared node, both methods return nullptr, because the two pointers reach the end together.
• Check for nullptr before moving a pointer with ->next.