Intersection of two sorted linked lists

Question

You are given the heads of two singly linked lists, each sorted ascending with distinct values. Return a sorted list of the values that appear in both, using a single lockstep walk.

l1: 1 -> 2 -> 4 -> 8
l2: 2 -> 4 -> 6 -> 8
->  2 -> 4 -> 8

Target $O(m + n)$ time and $O(1)$ extra space beyond the output.

Accepted Answer

Same two-pointer skeleton as a merge, but instead of always emitting the smaller front, you only emit when the two fronts are equal. When they differ, advance the pointer at the smaller value; it can never match anything still ahead in the other list, so discarding it is safe. Tracing the example: 1 < 2 so drop 1; 2 == 2 emit 2 and advance both; 4 == 4 emit 4; 8 6 so drop 6; 8 == 8 emit 8. Result 2 - 4 - 8. As soon as either list ends, no further matches are possible, so the loop stops. Time O(m + n); the two walkers never revisit a node. We allocate fresh nodes for the output (an intersectio…

Intersection of two sorted linked lists

Your answer

More Coding questions