Intersection of Two Linked Lists with Possible Cycles

Problem: Intersection of Two Singly Linked Lists with Possible Cycles You are given the head nodes headA and headB of two singly linked lists. Each list may contain a cycle or be acyclic. Implement a function to determine whether the two lists share at least one node (i.e., they intersect). If they intersect, return any shared node reference; otherwise return null. Requirements Aim for O(n + m) time complexity Aim for O(1) extra space You must handle all cases: Both lists are acyclic: may intersect or not One cyclic and one acyclic: cannot intersect Both cyclic: Disjoint cycles (no intersection) Same cycle (entry nodes may be the same or different), and they may also intersect before entering the cycle Constraints Number of nodes n, m: 1 ~ 2 * 10^5 Node values are irrelevant; intersection is based on reference equality Example Scenarios (structural) A: 1->2->3->4, B: 9->3->4 => return node 3 A: 1->2->3, B: 4->5 => return null A cyclic, B acyclic => return null Both cyclic, same entry => return a shared node (e.g., the entry) Both cyclic, different entries but same cycle => return any node on that cycle Example Input case1: A=1->2->3->4, B=9->(points to node 3) Output node with value 3 (shared reference)