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 test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
• listA - The first linked list.
• listB - The second linked list.
• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

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’

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: No intersection

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 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

Approach: Two Pointer with Length Alignment (Optimal Solution)

Algorithm

1. Compute the lengths of both lists
2. Advance the pointer of the longer list by the length difference
3. Now both pointers are the same distance from the end
4. Move both pointers in tandem
5. The first pointer pair that are equal is the intersection node
6. If no match is found, return null

Key Insight

Two lists that intersect share the same tail. If we align both pointers to the same distance from the end, then walking them together guarantees they meet at the intersection node if one exists.

Time & Space Complexity

• Time Complexity: O(m + n) - each list is traversed at most twice
• Space Complexity: O(1) - constant extra space used

Java Implementation

public class IntersectionOfTwoLinkedLists {

    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    /**
     * Find the node where two singly linked lists intersect.
     * @param headA Head of the first linked list
     * @param headB Head of the second linked list
     * @return The intersection node, or null if there is no intersection
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);

        // Align pointers to the same distance from the end
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }

        // Walk both pointers in tandem
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }

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

    // Helper method to build two lists that intersect
    public static ListNode buildIntersectingLists(int[] common, int[] prefixA, int[] prefixB) {
        // Returns the head of the common node
        ListNode commonHead = null;
        ListNode commonTail = null;
        for (int value : common) {
            ListNode node = new ListNode(value);
            if (commonHead == null) {
                commonHead = node;
            } else {
                commonTail.next = node;
            }
            commonTail = node;
        }
        return commonHead;
    }

    // Test method
    public static void main(String[] args) {
        // Build intersection node chain 8 -> 4 -> 5
        ListNode common = new ListNode(8);
        common.next = new ListNode(4);
        common.next.next = new ListNode(5);

        // List A: 4 -> 1 -> 8 -> 4 -> 5
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = common;

        // List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(1);
        headB.next.next.next = common;

        ListNode result = getIntersectionNode(headA, headB);
        System.out.println("Intersected at: " + (result == null ? "null" : String.valueOf(result.val))); // Expected: 8

        // Test case 3: no intersection
        ListNode a = new ListNode(2);
        a.next = new ListNode(6);
        a.next.next = new ListNode(4);
        ListNode b = new ListNode(1);
        b.next = new ListNode(5);
        ListNode result2 = getIntersectionNode(a, b);
        System.out.println("No intersection: " + (result2 == null ? "null" : String.valueOf(result2.val))); // Expected: null
    }
}

Example Walkthrough

For listA = [4,1,8,4,5] and listB = [5,6,1,8,4,5]:

1. lenA = 5, lenB = 6. Advance headB by 1 → starts at node 6
2. Compare: 4 vs 6, 1 vs 1, 8 vs 8. Match at node 8
3. Return node 8

Alternative Approach: Pointer Swap

public static ListNode getIntersectionNodeSwap(ListNode headA, ListNode headB) {
    ListNode pA = headA;
    ListNode pB = headB;

    while (pA != pB) {
        pA = (pA == null) ? headB : pA.next;
        pB = (pB == null) ? headA : pB.next;
    }

    return pA;
}

This elegant variant avoids computing lengths: each pointer traverses both lists (total length m + n), and if they intersect, they meet at the intersection; otherwise both reach null simultaneously and the loop ends.

Key Insights

1. Shared Tail: Intersecting lists share the same suffix, so aligning distances works
2. Length Difference: Advancing the longer list by the difference equalizes the remaining distances
3. Node Identity: Compares node references, not values, so nodes with equal values but different references are handled correctly
4. Original Structure: The algorithm only reads pointers, never modifying the lists

The length-alignment approach is the optimal solution, providing O(m + n) time with constant space.