Given the head nodes headA and headB of two singly linked lists, determine the node at which the two lists intersect. Return the intersecting node. If no intersection exists, return null.

The linked list structure is guraanteed to be acyclic. The original structure of both lists must remain unchanged after the function returns.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Explanation: The value of the intersecting node is 8. In listA, there are 2 nodes before the intersection; in listB, there are 3 nodes before the intersection.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Explanation: The value of the intersecting node is 2. In listA, there are 3 nodes before the intersection; in listB, there is 1 node before the intersection.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Explanation: The two lists do not intersect, so return null.

Constraints:

• The number of nodes in listA is m.
• The number of nodes in listB is n.
• 0 <= m, n <= 3 * 10^4
• 1 <= Node.val <= 10^5
• 0 <= skipA <= m
• 0 <= skipB <= n
• If the lists do not intersect, intersectVal is 0.
• If the lists intersect, intersectVal == listA[skipA] == listB[skipB] (0-indexed).

Follow-up: Could you write a soluiton that runs in O(m + n) time and uses O(1) memory?

// Approach 1: Using a HashSet
public ListNode findIntersection(ListNode headA, ListNode headB) {
    Set<ListNode> nodeSet = new HashSet<>();
    ListNode currentA = headA;
    while (currentA != null) {
        nodeSet.add(currentA);
        currentA = currentA.next;
    }
    ListNode currentB = headB;
    while (currentB != null) {
        if (nodeSet.contains(currentB)) {
            return currentB;
        }
        currentB = currentB.next;
    }
    return null;
}

// Approach 2: Comparing Lengths
public ListNode findIntersection(ListNode headA, ListNode headB) {
    int lenA = calculateLength(headA);
    int lenB = calculateLength(headB);
    ListNode ptrA = headA;
    ListNode ptrB = headB;
    if (lenA > lenB) {
        int diff = lenA - lenB;
        for (int i = 0; i < diff; i++) {
            ptrA = ptrA.next;
        }
    } else {
        int diff = lenB - lenA;
        for (int i = 0; i < diff; i++) {
            ptrB = ptrB.next;
        }
    }
    while (ptrA != ptrB) {
        ptrA = ptrA.next;
        ptrB = ptrB.next;
    }
    return ptrA;
}

private int calculateLength(ListNode head) {
    int count = 0;
    ListNode current = head;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

// Approach 3: Two Pointers
public ListNode findIntersection(ListNode headA, ListNode headB) {
    ListNode pointerA = headA;
    ListNode pointerB = headB;
    while (pointerA != pointerB) {
        pointerA = (pointerA == null) ? headB : pointerA.next;
        pointerB = (pointerB == null) ? headA : pointerB.next;
    }
    return pointerA;
}