Intersection of Two Linked Lists easy

Problem Statement

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

For example, the following two linked lists begin to intersect at node c1:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

Constraints:

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 1 <= m, n <= 3 * 10^4
• 1 <= Node.val <= 10^5
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if there is no intersected node.
• intersectVal is the val of the intersected node if listA and listB intersect.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'

Steps:

1. Traverse both lists: Iterate through both linked lists headA and headB simultaneously.
2. Different Lengths Handling: If the lists have different lengths, after reaching the end of the shorter list, continue traversal from the head of the other list.
3. Intersection Detection: The point where the pointers meet is the intersection node (if any). If the pointers reach the end of both lists without meeting, there is no intersection.

Explanation:

The key idea is that if two lists intersect, the tails of both lists will eventually point to the same node. By traversing both lists simultaneously, and switching to the other list when reaching the end of one, we ensure that both pointers traverse an equal number of nodes after the intersection point, if it exists. If they never meet, it means there's no intersection.

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ptrA = headA;
        ListNode ptrB = headB;

        while (ptrA != ptrB) {
            if (ptrA == null) {
                ptrA = headB;
            } else {
                ptrA = ptrA.next;
            }

            if (ptrB == null) {
                ptrB = headA;
            } else {
                ptrB = ptrB.next;
            }
        }

        return ptrA; 
    }
}

Complexity:

• Time Complexity: O(m + n), where m and n are the lengths of listA and listB respectively. We traverse each list at most once.
• Space Complexity: O(1). We only use a constant amount of extra space to store pointers.