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 theshared 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 nodesSample 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