Intersection of Two Linked Lists
Easy · Linked Lists · Hash Table · Linked List · Two Pointers
Problem
You are given the heads of two singly linked lists, headA and headB. The lists may join: from some node on, they continue through the very same nodes to the end. Return that first shared node, or None if the lists never meet.
Shared means the same node object, not an equal value. Two different nodes can hold the same number, so a.val == b.val does not mean the lists have met; a is b does. Neither list has a cycle, and both must keep their structure: do not relink any node.
In the tests, crossed(a, b, shared, 'a') builds list A — nodes holding the values a, followed by nodes holding shared — and crossed(a, b, shared, 'b') builds list B, which ends in those same shared nodes. Results show a node by its value and its index on each list, such as val 8 at A[2] and B[3].
Follow-up: can you do it in O(m + n) time with O(1) extra memory?
Examples
Input: headA = 4 -> 1 -> 8 -> 4 -> 5, headB = 5 -> 6 -> 1 -> 8 -> 4 -> 5, sharing the last three nodes Output: val 8 at A[2] and B[3]
The lists join at the node holding 8. Each list also holds a 1 before that, but in two different nodes: equal values, not the same node.
Input: headA = 2 -> 6 -> 4, headB = 1 -> 5, no shared nodes Output: None
The lists end separately, so there is no node they share.
Constraints
- 1 <= m, n <= 3 * 10^4 (the numbers of nodes in A and B)
- 1 <= Node.val <= 10^5
- Neither list has a cycle
- If the lists meet, every node from the first shared one to the end is shared
Approaches
- Remember every node of A — time O(m + n), space O(m)
Follow-up
Could you do it in O(m + n) time with only O(1) extra memory?
Related problems
Start free on Cariara · Coding problems · System design studio
