Intersection of Two Linked Lists

Given the heads of two singly linked lists headA and headB, return the value of the node at which the two lists intersect. If the two linked lists have no intersection, return null.

The parameter skipA indicates how many nodes to skip in list A before the intersection begins, and skipB indicates how many nodes to skip in list B. The shared suffix starting at those positions represents the intersection.

Examples

Example 1:

Input: headA = [4,1,8,4,5], headB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output: 8

Explanation: The two lists intersect at the node with value 8. List A has 2 nodes before the intersection, list B has 3 nodes before it.

Example 2:

Input: headA = [1,9,1,2,4], headB = [3,2,4], skipA = 3, skipB = 1

Output: 2

Explanation: The two lists intersect at the node with value 2.

Example 3:

Input: headA = [2,6,4], headB = [1,5], skipA = 3, skipB = 2

Output: null

Explanation: The two lists do not intersect since skipA equals the length of list A.

Constraints

• The number of nodes in list A is in the range [1, 3 * 10⁴]
• The number of nodes in list B is in the range [1, 3 * 10⁴]
• 1 <= Node.val <= 10⁵
• 0 <= skipA < listA.length
• 0 <= skipB < listB.length
• The intersection is guaranteed to be valid when it exists