Problem Description

• LeetCode 160: Intersection of Two Linked Lists

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. The linked lists must retain their original structure after the function returns, and you may assume there are no cycles anywhere in the entire linked structure.

Solution 1: HashMap Approach

Core Idea: Store all nodes from one list in a hash set, then traverse the second list to find the first common node.

Algorithm:

1. Traverse the first linked list and store all node references in a HashSet
2. Traverse the second linked list and check if each node exists in the HashSet
3. Return the first node found in the HashSet, or null if none exists

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;

    Set<ListNode> visitedNodes = new HashSet<>();

    // Store all nodes from list A
    ListNode current = headA;
    while (current != null) {
        visitedNodes.add(current);
        current = current.next;
    }

    // Check each node in list B
    current = headB;
    while (current != null) {
        if (visitedNodes.contains(current)) {
            return current;
        }
        current = current.next;
    }

    return null;
}

Complexity:

• Time: O(m + n) - traverse both lists once
• Space: O(m) - store all nodes from first list

Solution 2: Length Calculation with Alignment

Core Idea: Calculate both list lengths, align the starting positions, then traverse simultaneously until intersection is found.

Algorithm:

1. Calculate the length of both linked lists
2. Move the pointer of the longer list forward by the difference in lengths
3. Move both pointers simultaneously until they meet

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;

    // Calculate lengths
    int lenA = getLength(headA);
    int lenB = getLength(headB);

    // Align starting positions
    while (lenA > lenB) {
        headA = headA.next;
        lenA--;
    }
    while (lenB > lenA) {
        headB = headB.next;
        lenB--;
    }

    // Move both pointers until they meet
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }

    return headA;
}

private int getLength(ListNode head) {
    int length = 0;
    while (head != null) {
        length++;
        head = head.next;
    }
    return length;
}

Complexity:

• Time: O(m + n) - three passes through the lists
• Space: O(1) - only using pointers

Solution 3: Two-Pointer without Length Calculation

Core Idea: Use the mathematical property that if two pointers traverse both lists completely, they will meet at the intersection point.

Algorithm:

1. Start two pointers at the heads of both lists
2. When a pointer reaches the end, redirect it to the head of the other list
3. Continue until both pointers meet

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;

    ListNode a = headA;
    ListNode b = headB;

    // If a & b have different lengths, then we will stop the loop after second iteration
    while (a != b) {
        // For the end of first iteration, we just reset the pointer to the head of another linkedlist
        a = a == null ? headB : a.next;
        b = b == null ? headA : b.next;
    }

    return a;
}

Mathematical Insight:

• Distance traveled by pointer A: (m - c) + n + (n - c) = m + n - c
• Distance traveled by pointer B: (n - c) + m + (m - c) = m + n - c
• Both pointers travel the same distance and meet at intersection!

Complexity:

• Time: O(m + n) - each pointer traverses at most both lists once
• Space: O(1) - only using two pointers

Solution 4: Brute Force Approach

Core Idea: For each node in the first list, traverse the entire second list to check for intersection.

Algorithm:

1. For each node in list A, traverse the entire list B
2. If any node in B matches the current node in A, return it
3. If no match is found after checking all nodes, return null

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;

    ListNode currentA = headA;

    // For each node in list A
    while (currentA != null) {
        ListNode currentB = headB;

        // Check against all nodes in list B
        while (currentB != null) {
            if (currentA == currentB) {
                return currentA;
            }
            currentB = currentB.next;
        }
        currentA = currentA.next;
    }

    return null;
}

Complexity:

• Time: O(m × n) - for each node in A, traverse all of B
• Space: O(1) - only using pointers

Comparison and Analysis

Best Choice: Solution 3 (Two-Pointer) is generally preferred due to its optimal time/space complexity and elegant approach, though Solution 2 might be easier to understand in interviews.

Key Insight: The intersection problem beautifully demonstrates how mathematical properties can lead to surprisingly elegant algorithmic solutions, transforming what seems like a complex problem into a simple two-pointer technique.