Intersection of Two Linked Lists

How it works

A clever approach avoids computing lengths explicitly. Two pointers start at the heads of each list. When a pointer reaches the end, it jumps to the head of the other list. After at most m + n steps, both pointers will have traversed the same total distance. If an intersection exists, they will meet there; otherwise, they both reach null simultaneously.

Steps

1. Initialize l1 = headA and l2 = headB.
2. While l1 != l2:
   • If l1 is null, set l1 = headB; otherwise advance l1.
   • If l2 is null, set l2 = headA; otherwise advance l2.
3. Return l1 (which equals l2), the intersection node or null.

Complexity

• Time complexity: O(m + n)
• Space complexity: O(1) extra space.

Where m is the length of the first list and n is the length of the second list.

Things to watch for

Comparing Node Values Instead of References

Intersection means the lists share the same node object, not just nodes with equal values. Using nodeA.val == nodeB.val will give false positives. You must compare node references directly (nodeA == nodeB or nodeA === nodeB in JavaScript) to correctly identify shared nodes.

Not Handling Non-Intersecting Lists

When two lists do not intersect, the two-pointer approach naturally terminates when both pointers become null simultaneously. However, some implementations create infinite loops by not properly handling the case where pointers should redirect to the other list's head. Ensure your loop condition checks for pointer equality including the null == null case.

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        l1, l2 = headA, headB
        while l1 != l2:
            l1 = l1.next if l1 else headB
            l2 = l2.next if l2 else headA
        return l1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* l1 = headA;
        ListNode* l2 = headB;
        while (l1 != l2) {
            l1 = l1 ? l1->next : headB;
            l2 = l2 ? l2->next : headA;
        }
        return l1;
    }
};