Intersection Point of Two Linked Lists in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the intersection node value

Given two singly linked lists that intersect, what is the value of the intersection node printed by the 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 a: ListNode | null = headA;
  let b: ListNode | null = headB;
  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
  return a;
}

// Creating intersecting lists
const intersect = new ListNode(8, new ListNode(10));
const listA = new ListNode(3, new ListNode(7, intersect));
const listB = new ListNode(99, new ListNode(1, intersect));

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

A 10

B 8

C 7

D null

💡 Hint

Trace the pointers moving through each list and switching heads when reaching the end.

The function moves two pointers through both lists. When one pointer reaches the end, it switches to the other list's head. They meet at the intersection node with value 8.

❓ Predict Output

intermediate

Output when no intersection exists

What does the following code print when two linked lists do NOT intersect?

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 a: ListNode | null = headA;
  let b: ListNode | null = headB;
  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
  return a;
}

const listA = new ListNode(1, new ListNode(2, new ListNode(3)));
const listB = new ListNode(4, new ListNode(5));

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

A null

B 3

C 5

D 1

💡 Hint

If lists do not share nodes, pointers will both become null eventually.

Since the lists do not intersect, the pointers will both become null after traversing both lists, so the function returns null.

🔧 Debug

advanced

Identify the error in intersection detection

What error does the following code produce when trying to find the intersection point of two linked lists?

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 {
  let a: ListNode | null = headA;
  let b: ListNode | null = headB;
  while (a !== b) {
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
  return a;
}

const intersect = new ListNode(7);
const listA = new ListNode(1, new ListNode(2, intersect));
const listB = new ListNode(3, intersect);

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

A null

B 7

C TypeError: Cannot read property 'next' of null

D Infinite loop

💡 Hint

Check what happens when a or b is null before accessing .next

The code tries to access a.next or b.next without checking if a or b is null, causing a TypeError.

❓ Predict Output

advanced

Length difference approach output

What is the output of the code that finds the intersection node by first calculating lengths and then aligning the start pointers?

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 getLength(head: ListNode | null): number {
  let length = 0;
  let current = head;
  while (current) {
    length++;
    current = current.next;
  }
  return length;
}

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  let lenA = getLength(headA);
  let lenB = getLength(headB);
  let a = headA;
  let b = headB;

  while (lenA > lenB) {
    a = a!.next;
    lenA--;
  }
  while (lenB > lenA) {
    b = b!.next;
    lenB--;
  }

  while (a !== b) {
    a = a!.next;
    b = b!.next;
  }
  return a;
}

const intersect = new ListNode(15, new ListNode(30));
const listA = new ListNode(10, new ListNode(12, intersect));
const listB = new ListNode(3, intersect);

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

A 15

B null

C 12

D 30

💡 Hint

Align the longer list's pointer to the same distance from the end as the shorter list.

The code aligns the pointers by skipping nodes in the longer list, then moves both pointers until they meet at the intersection node with value 15.

🧠 Conceptual

expert

Why does the two-pointer approach guarantee intersection detection?

Why does the two-pointer approach (switching heads when reaching the end) always find the intersection node or return null if none exists?

A Because the pointers only traverse the shorter list twice to find the intersection.

B Because the pointers use extra memory to store visited nodes and detect cycles.

C Because the pointers compare node values instead of references to find intersection.

D Because both pointers traverse the combined length of both lists, aligning them to meet at the intersection or end simultaneously.

💡 Hint

Think about how switching heads equalizes the path lengths.

By switching heads, each pointer traverses both lists fully, so they align in distance from the intersection or end, ensuring they meet at the intersection or both become 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