Intersection of Two Linked Lists

Share

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 lists are guaranteed to have no cycles. Note that the linked lists must retain their original structure after the function returns.

Example 1
Input: listA = [4, 1, 8, 4, 5], listB = [5, 6, 1, 8, 4, 5]
Output: Node with value 8
Explanation: The intersected node has value 8. Lists share the suffix [8, 4, 5].
Example 2
Input: listA = [2, 6, 4], listB = [1, 5]
Output: null
Explanation: The two lists do not intersect.

Solution Approach - Two Pointer Trick

The elegant O(1) space approach uses two pointers pA and pB starting at the heads of their respective lists. When a pointer reaches the end of its list, it is redirected to the head of the other list. Both pointers will meet at the intersection node (or both become null at the same time if no intersection exists).

Why does this work? If list A has length a and list B has length b, and the shared tail has length c, then pointer A travels a + (b - c) before reaching the intersection and pointer B travels b + (a - c). Both distances are equal, so they meet at the intersection node.

  • Initialize pA = headA and pB = headB.
  • Advance each pointer one step. When a pointer reaches null, redirect it to the other list's head.
  • If both pointers are equal (even if both null), return that node (or null if no intersection).
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class IntersectionOfTwoLinkedLists {

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

        // Both pointers traverse a + b total nodes, so they meet at intersection
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA; // either the intersection node or null
    }
}
Complexity Analysis:

Time complexity: O(m + n) where m and n are the lengths of the two lists. Each pointer traverses at most m + n nodes.
Space complexity: O(1) as only two pointer variables are used.