Intersection of Two Linked Lists
EasyP2Coding
Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect, or null if they do not intersect.
Two lists intersect when they share the same node objects from some point to the end, not just equal values. The lists contain no cycles, and you must not change their structure.
How the tests build the input: headA is a normal list. headB is written as {"list": [5, 6, 1], "join": 2}, meaning its own nodes 5, 6, 1 followed by headA's node at index 2 and everything after it. join: -1 means the lists share nothing. The result is checked by the value of the node you return (null for no intersection).
Example 1
- Input
- headA = [4,1,8,4,5], headB = {"list":[5,6,1],"join":2}
- Output
- 8
- Why
- B is 5 → 6 → 1 → (A's 8) → 4 → 5. Both lists have a node with value 1 before 8, but they are different nodes; the first shared node is 8.
Example 2
- Input
- headA = [1,9,1,2,4], headB = {"list":[3],"join":3}
- Output
- 2
Example 3
- Input
- headA = [2,6,4], headB = {"list":[1,5],"join":-1}
- Output
- null
Constraints
- 0 <= length of each list <= 3 * 10^4
- 1 <= Node.val <= 10^5
- No cycles; do not modify either list.
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.