Intersection Point of Two Linked Lists in DSA Typescript

Mental Model

Two linked lists may share some nodes at the end. We want to find the first shared node where they meet.

Analogy: Imagine two roads that start separately but merge into one road at some point. We want to find the exact spot where the two roads join.

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
                     ↑
List B:       9 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: List A: 1->2->3->4->5, List B: 9->4->5 (4 and 5 are shared nodes)

Goal: Find the first node where both lists intersect, which is node with value 4

Step 1: Set pointerA to head of List A (node 1), pointerB to head of List B (node 9)

pointerA -> 1 -> 2 -> 3 -> 4 -> 5 -> null
pointerB -> 9 -> 4 -> 5 -> null

Why: Start traversing both lists from their heads

Step 2: 1 != 9, advance pointerA to 2, pointerB to 4

pointerA -> 2 -> 3 -> 4 -> 5 -> null
pointerB -> 4 -> 5 -> null

Why: Nodes differ, move both pointers forward

Step 3: 2 != 4, advance pointerA to 3, pointerB to 5

pointerA -> 3 -> 4 -> 5 -> null
pointerB -> 5 -> null

Why: Continue moving pointers to find matching node

Step 4: 3 != 5, advance pointerA to 4, pointerB reaches null so reset to head of List A (1)

pointerA -> 4 -> 5 -> null
pointerB -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: When pointerB reaches end, switch to headA to align lengths

Step 5: 4 != 1, advance pointerA to 5, pointerB to 2

pointerA -> 5 -> null
pointerB -> 2 -> 3 -> 4 -> 5 -> null

Why: Nodes differ, continue traversal

Step 6: 5 != 2, advance pointerA reaches null so reset to head of List B (9), pointerB to 3

pointerA -> 9 -> 4 -> 5 -> null
pointerB -> 3 -> 4 -> 5 -> null

Why: When pointerA reaches end, switch to headB

Step 7: 9 != 3, advance pointerA to 4, pointerB to 4

pointerA -> 4 -> 5 -> null
pointerB -> 4 -> 5 -> null

Why: Pointers now point to the same node

Step 8: pointerA === pointerB at node 4, intersection found

pointerA -> [4] -> 5 -> null
pointerB -> [4] -> 5 -> null

Why: Pointers meet at the intersection node, loop exits and return node 4

Result:

4 -> 5 -> null is the intersection point

Annotated Code

DSA Typescript

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  if (!headA || !headB) return null;
  let pointerA: ListNode | null = headA;
  let pointerB: ListNode | null = headB;

  while (pointerA !== pointerB) {
    pointerA = pointerA ? pointerA.next : headB; // switch to headB when reaching end of A
    pointerB = pointerB ? pointerB.next : headA; // switch to headA when reaching end of B
  }
  return pointerA; // either intersection node or null
}

// Driver code to create lists and test
// Shared nodes
const shared3 = new ListNode(5);
const shared2 = new ListNode(4, shared3);

// List A: 1 -> 2 -> 3 -> 4 -> 5
const headA = new ListNode(1, new ListNode(2, new ListNode(3, shared2)));

// List B: 9 -> 4 -> 5
const headB = new ListNode(9, shared2);

const intersection = getIntersectionNode(headA, headB);
if (intersection) {
  let curr: ListNode | null = intersection;
  let result = '';
  while (curr) {
    result += curr.val + ' -> ';
    curr = curr.next;
  }
  result += 'null';
  console.log(result);
} else {
  console.log('null');
}

while (pointerA !== pointerB) {

loop until pointers meet or both become null

pointerA = pointerA ? pointerA.next : headB;

advance pointerA or switch to headB if reached end

pointerB = pointerB ? pointerB.next : headA;

advance pointerB or switch to headA if reached end

return pointerA;

return intersection node or null if no intersection

Output

4 -> 5 -> null

Complexity Analysis

Time: O(m + n) because each pointer traverses both lists at most once

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Naive approach compares every node of one list with every node of the other, which is O(m*n), much slower

Edge Cases

One or both lists are empty

Function returns null immediately

DSA Typescript

if (!headA || !headB) return null;

Lists do not intersect

Pointers both reach null and function returns null

DSA Typescript

while (pointerA !== pointerB) { ... }

Intersection at head node

Function returns head node immediately

DSA Typescript

while (pointerA !== pointerB) { ... }

When to Use This Pattern

When you see two linked lists and need to find if and where they join, use the two-pointer switching technique to align traversal lengths and find intersection efficiently.

Common Mistakes

Mistake: Not switching pointers to the other list's head after reaching end, causing infinite loop or wrong result
Fix: Switch pointer to the other list's head when it reaches null to align traversal lengths

Mistake: Comparing node values instead of node references to find intersection
Fix: Compare nodes by reference (pointer equality), not by value

Summary

Finds the first shared node where two linked lists intersect.

Use when you need to detect if two linked lists merge and find the merge point.

Switching pointers to the other list's head aligns traversal lengths so pointers meet at intersection or null.

Practice

1. What does the "Intersection Point of Two Linked Lists" problem ask you to find?

easy

A. The node where two linked lists merge or intersect

B. The sum of all nodes in both linked lists

C. The length of the longer linked list

D. The first node of the longer linked list

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the node where two linked lists join or share the same reference, not just the value.

2. Step 2: Clarify what intersection means

   Intersection means the exact same node object, not just nodes with equal values.

3. Final Answer:

   The node where two linked lists merge or intersect -> Option A

4. Quick Check:

   Intersection point = node shared by both lists [OK]

Hint: Look for the shared node reference, not just values [OK]

Common Mistakes:

• Confusing intersection with nodes having same values
• Thinking intersection means equal length lists
• Looking for sum or length instead of node

2. Which TypeScript syntax correctly declares a singly linked list node class for this problem?

easy

A. type ListNode = { val: number; next: ListNode | undefined }

B. function ListNode(val) { this.val = val; this.next = null; }

C. interface ListNode { val: number; next: ListNode; }

D. class ListNode { val: number; next: ListNode | null; constructor(val: number) { this.val = val; this.next = null; } }

Solution

1. Step 1: Check for class declaration with constructor

   class ListNode { val: number; next: ListNode | null; constructor(val: number) { this.val = val; this.next = null; } } correctly defines a class with a constructor initializing val and next properties.

2. Step 2: Verify type safety and nullability

   class ListNode { val: number; next: ListNode | null; constructor(val: number) { this.val = val; this.next = null; } } uses 'next: ListNode | null' which is correct for linked list end.

3. Final Answer:

   class ListNode { val: number; next: ListNode | null; constructor(val: number) { this.val = val; this.next = null; } } -> Option D

4. Quick Check:

   Proper class with constructor and nullable next [OK]

Hint: Use class with constructor and nullable next for nodes [OK]

Common Mistakes:

• Using interface without constructor
• Missing null for next pointer
• Using function syntax without types

3. Given the following TypeScript code, what will be the output printed?

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

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

// Create nodes
const common = new ListNode(8);
common.next = new ListNode(10);

const listA = new ListNode(3);
listA.next = new ListNode(7);
listA.next.next = common;

const listB = new ListNode(99);
listB.next = common;

const intersection = getIntersectionNode(listA, listB);
console.log(intersection ? intersection.val : null);

medium

A. 7

B. 10

C. 8

D. null

Solution

1. Step 1: Trace the linked lists and intersection node

   List A: 3 -> 7 -> 8 -> 10; List B: 99 -> 8 -> 10; common intersection starts at node with value 8.

2. Step 2: Understand the two-pointer approach

   Pointers pA and pB traverse each list; when one reaches end, it switches to the other list's head. They meet at intersection node 8.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   Intersection node value = 8 [OK]

Hint: Two pointers meet at intersection or null if none [OK]

Common Mistakes:

• Returning node value 7 or 10 instead of 8
• Confusing node values with references
• Not switching pointers to other list head

4. Identify the bug in this TypeScript function to find the intersection point of two linked lists:

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  let pA = headA;
  let pB = headB;
  while (pA !== pB) {
    pA = pA.next;
    pB = pB.next;
    if (!pA && !pB) return null;
  }
  return pA;
}

medium

A. Pointers do not switch to the other list's head after reaching null

B. The function returns null too early when both pointers are null

C. The while loop condition should be pA == pB instead of !==

D. The function does not handle empty lists

Solution

1. Step 1: Analyze pointer movement in the loop

   Both pointers move forward but do not switch to the other list's head when reaching null, so they may never meet.

2. Step 2: Understand the standard approach

   To find intersection, pointers must switch to the other list's head after reaching null to align lengths.

3. Final Answer:

   Pointers do not switch to the other list's head after reaching null -> Option A

4. Quick Check:

   Switch pointers to other list head to find intersection [OK]

Hint: Switch pointers to other list head on null to align [OK]

Common Mistakes:

• Not switching pointers causes infinite loop or wrong result
• Returning null too early without full traversal
• Incorrect loop condition

5. You have two singly linked lists that intersect at some node. List A has length 7, List B has length 5, and they share the last 3 nodes. Which approach correctly finds the intersection point efficiently?

hard

A. Traverse both lists fully and compare node values at each step

B. Calculate lengths, advance longer list by difference, then move both pointers together

C. Reverse both lists and compare from the start

D. Use a hash set to store all nodes of the shorter list and check nodes of the longer list

Solution

1. Step 1: Calculate lengths and difference

   List A length = 7, List B length = 5, difference = 2.

2. Step 2: Advance longer list pointer by difference

   Move pointer in List A forward by 2 nodes to align with List B pointer.

3. Step 3: Move both pointers together to find intersection

   Advance both pointers step-by-step until they meet at the intersection node.

4. Final Answer:

   Calculate lengths, advance longer list by difference, then move both pointers together -> Option B

5. Quick Check:

   Align pointers by length difference to find intersection [OK]

Hint: Advance longer list by length difference before simultaneous traversal [OK]

Common Mistakes:

• Comparing node values instead of references
• Reversing lists wastes time and breaks structure
• Using hash set wastes extra space unnecessarily