Intersection of Two Linked Lists

Problem Statement

Given the heads of two singly linked lists headA and headB, return the node where the two lists intersect. If no intersection, return NULL.

Example: Input: A = 4 → 1 → 8 → 4 → 5, B = 5 → 6 → 1 → 8 → 4 → 5, Output: Node with value 8

Approach 1: Hash Set

Explanation: Store nodes of first list in a set. Traverse second list, first common node is intersection.

Time Complexity: O(m+n)

Space Complexity: O(m)

Function getIntersectionNode(headA, headB):
    Create an empty set called visitedNodes

    // Traverse list A and store each node reference
    While headA is not null:
        Add headA to visitedNodes
        headA = headA.next

    // Traverse list B and check for intersection
    While headB is not null:
        If headB exists in visitedNodes:
            Return headB  // Intersection found
        headB = headB.next

    Return null  // No intersection

Approach 2: Two Pointer Technique

Explanation: Traverse both lists. When one reaches end, redirect to other list’s head. They will meet at intersection.

Time Complexity: O(m+n)

Space Complexity: O(1)

Function getIntersectionNode(headA, headB):
    Set pointerA = headA
    Set pointerB = headB

    While pointerA is not equal to pointerB:
        If pointerA is null:
            pointerA = headB
        Else:
            pointerA = pointerA.next

        If pointerB is null:
            pointerB = headA
        Else:
            pointerB = pointerB.next

    Return pointerA  // Either the intersection node or null