Given the heads of two non-empty singly linked lists, headA and headB, return the first node at which the two lists begin to share the same chain of nodes. After that point, every following node is the same object in both lists.
Two nodes are considered equal only when they are the same object in memory. Two distinct node objects with the same val do not indicate an intersection.
If the lists do not share any node, return null.
Neither linked list contains a cycle. Return the actual node object; examples display the value inside the returned node for readability.
Your solution must run in time and use only extra space, where m is the length of the list beginning at headA and n is the length of the list beginning at headB.
Example 1:
Input: listA = [2,6,4,3,7], listB = [1,5,3,7]
Output: 3
Explanation: The suffix nodes with values 3 and 7 are physically the same nodes in both lists, so the first shared node has value 3.
listA = [2,6, 4, 3, 7] listB = [1, 5, 3, 7]
3
Input: listA = [2,6,4,3,7] and listB = [1,5,3,7].
Example 2:
Input: listA = [9,4,2], listB = [7,8]
Output: null
Explanation: These two chains contain no node that is shared by reference.
Example 3:
Input: listA = [5,9], listB = [5,9]
Output: 5
Explanation: Here headA and headB reference the same first node, so the entire chain is shared and the intersection node has value 5.
Constraints:
headA and headB are non-null.val.listA = [2,6, 4, 3, 7] listB = [1, 5, 3, 7]
3
Input: listA = [2,6,4,3,7] and listB = [1,5,3,7].