Intersection of Two Linked Lists

Overview

Intersection of two linked lists means finding the first node that is common to both lists (the same node by reference, not just value). After the intersection point, both lists share the same nodes until the end. The lists may have different lengths before the intersection. The goal is to find that node in O(n + m) time and O(1) space.

Key idea: If we align the two lists so we start comparing from positions that are the same distance from the end, we can walk in lockstep until we find the same node (or reach the end). Two approaches: (1) compute lengths, advance the longer list by the length difference, then step both together; (2) use two pointers that switch to the other list's head when they hit null (so they align after one "lap" each).

When to Use

• Find intersection node — Two lists that may merge into one; return the merge point.
• Cycle / shared structure — Same pattern when two paths join in a common tail.

How It Works

Approach A — Length alignment:

1. Traverse both lists to get lengths L1 and L2.
2. Advance the longer list's pointer by |L1 - L2| steps.
3. Move both pointers one step at a time until they point to the same node (or both become null).

Approach B — Two pointers, switch lists:

1. Pointer p starts at headA, q at headB.
2. Each step: if p is null, set p = headB; else p = p.next. If q is null, set q = headA; else q = q.next.
3. After each has traversed list A + list B (possibly with different segment lengths), they align: if there is an intersection they meet at the intersection node; otherwise both become null together.

Example 1: Length Alignment

Problem: Given the heads of two singly linked lists that may intersect, return the intersection node. If they do not intersect, return null.

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  const len = (h: ListNode | null) => {
    let n = 0;
    for (let p = h; p !== null; p = p.next) n++;
    return n;
  };
  let la = len(headA), lb = len(headB);
  let a: ListNode | null = headA;
  let b: ListNode | null = headB;
  if (la < lb) { [a, b, la, lb] = [headB, headA, lb, la]; }
  for (let i = 0; i < la - lb; i++) a = a!.next;
  while (a !== null && b !== null) {
    if (a === b) return a;
    a = a!.next;
    b = b!.next;
  }
  return null;
}

• Time: O(n + m), Space: O(1).

Example 2: Two Pointers, Switch Lists (No Length)

Problem: Same; do not compute lengths.

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  let p: ListNode | null = headA;
  let q: ListNode | null = headB;
  while (p !== q) {
    p = p === null ? headB : p.next;
    q = q === null ? headA : q.next;
  }
  return p;
}

• When there is no intersection, both eventually become null after each has traversed A + B, so the loop exits with p === q === null.
• Time: O(n + m), Space: O(1).

Edge Cases

• No intersection — Both lists end in null; return null. Both approaches handle this.
• Same list — headA === headB; intersection is the head.
• One list is a suffix of the other — Shorter list is entirely shared; intersection is the head of the shorter list.
• One list empty — No intersection; return null.

Common Mistakes

1. Comparing values — You must compare node identity (p === q), not p.val === q.val; different nodes can have the same value.
2. Infinite loop — In the switch-list approach, you must advance when not null; when null, switch to the other head so both eventually traverse A + B and exit.
3. Wrong length math — When aligning by length, advance the longer list by (longer - shorter) so the remaining lengths are equal.

Time and Space Complexity

• Time: O(n + m) for both approaches.
• Space: O(1).

Summary

• Intersection: Align by length then step together, or use two pointers that switch to the other list's head when null so they meet at the intersection (or both null).
• Compare by reference (===), not value.

See Dummy Head only if you need to build a new list; here we only traverse and compare.