Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Intersection of Two Linked Lists

Problem (restated)

Return the intersection node of two singly linked lists, or null.

Intuition

When a pointer ends, jump to the other list’s head. distances equalize at the intersection.

Approaches

Two-pointer switch heads

Unverified

Time O(m+n)Space O(1)

Idea. Advance a and b; null → switch head; stop when a == b.

Walkthrough. Shared tail of length c: both meet after a+c+b steps.

Trade-offs. Hash set of list A is simpler O(m) space.

Solution

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
export function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  if (!headA || !headB) return null;
  let a: ListNode | null = headA, b: ListNode | null = headB;
  while (a !== b) { a = a ? a.next : headB; b = b ? b.next : headA; }
  return a;
}

export class ListNode {
  val: number; next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
export function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  if (!headA || !headB) return null;
  let a: ListNode | null = headA, b: ListNode | null = headB;
  while (a !== b) { a = a ? a.next : headB; b = b ? b.next : headA; }
  return a;
}

Template connection

Two pointers that switch heads so the walks equalize at the intersection (same family as cycle detection).

Reflection

Switching each pointer onto the other list’s head lines the tails up. Why does that cancel the length difference?
With no intersection both pointers land on null together. Is an early null return a false positive?
Is node equality by reference or by value? Same value, different node.