Linked List · 111Easy
Intersection of Two Linked Lists
Given the heads of two singly linked lists, return the node where they intersect, or null if they never do. Intersection is by NODE IDENTITY, not value. Aim for O(1) extra space.
Constraints
- The lists hold 1 to 3 * 10^4 nodes each.
- 1 <= Node.val <= 10^5
- The lists retain their original structure.
- INPUT FORMAT
- `head` is a ListNode object, not an array. The arrays in EXAMPLES list the node values in
- order; the test runner links them into real nodes before calling your function.
Examples
listA = 4 -> 1 -> 8 -> 4 -> 5, listB = 5 -> 6 -> 1 -> 8 -> 4 -> 5 getIntersectionNode(listA, listB) -> the node holding 8 Two entirely separate lists -> null listA = 1 -> 9 -> 1 -> 2 -> 4, listB = 3 -> 2 -> 4, sharing the 2 -> 4 tail getIntersectionNode(listA, listB) -> the node holding 2 Both heads are the very same node 7 -> that node // a list may intersect at its head listA = 1 -> 3, listB is listA's second node getIntersectionNode(listA, listB) -> the node holding 3 listA = 1 -> 1 -> 1 -> 1, listB = 1 -> 1 -> 1, sharing only the last node getIntersectionNode(listA, listB) -> that last node // equal values prove nothing
Edge cases
- Lists of different lengths — the classic difficulty.
- Equal values do not imply intersection; compare node references.
- No intersection must return null, not a value.
Show the target complexity (spoiler)
- Naive
- O(m * n) time — compare every node of A against every node of B. O(n) space if you
- Target
- O(m + n) time, O(1) space — walk both lists, and on reaching the end switch to the other list's head; the pointers meet at the intersection (or both hit null).
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/06-linked-list/111-intersection-of-two-linked-lists.js ./practice c 111