codejump
MediumPythonJavaScriptTypeScript

Linked List — Intersection of Two Lists

Data StructuresLinked ListTwo Pointers

Two singly linked lists can share a tail: from some node on they are the very same
nodes. solve(prefixA, prefixB, shared) builds list A as prefixA followed by the
shared nodes, and list B as prefixB followed by the same shared nodes. Return
the value of the first shared node, or null when shared is empty (the lists never
meet).

Compare nodes, not values: [2,4] and [2,4] built separately have equal values but
share nothing. Use O(1) extra space with the *switch heads* trick: walk a pointer on each
list, and when one falls off the end, restart it on the *other* list's head. Both pointers
then travel lenA + lenB nodes and meet at the intersection (or both become null).

Examples

solve([4,1], [5,6,1], [8,4,5])  → 8
solve([1], [2], [])             → null
solve([2,4], [2,4], [])         → null     // equal values, different nodes

Sample tests

Test #1Classic example
Input: [[4,1],[5,6,1],[8,4,5]]
Output: 8
Test #2Lists never meet
Input: [[1],[2],[]]
Output: null
Test #3Equal values, different nodes
Input: [[2,4],[2,4],[]]
Output: null