Why Intersection Point of Two Linked Lists in DSA Typescript?

The Big Idea

Discover the clever trick that finds where two linked lists meet without checking every node!

The Scenario

Imagine you have two separate train tracks that suddenly merge into one track at some point. You want to find exactly where they join. Doing this by walking along each track and comparing every single rail piece manually would take a lot of time and effort.

The Problem

Manually checking each node of two linked lists to find where they intersect means comparing every node from one list with every node from the other. This is slow and tiring, especially if the lists are long. It's easy to make mistakes and miss the exact joining point.

The Solution

The Intersection Point of Two Linked Lists concept helps us find the exact node where two lists merge by smartly traversing both lists without extra memory or repeated comparisons. It uses a clever trick to align the lists and find the join point quickly and reliably.

Before vs After

✗ Before

for (let nodeA of listA) {
  for (let nodeB of listB) {
    if (nodeA === nodeB) return nodeA;
  }
}
return null;

✓ After

let pointerA = headA;
let pointerB = headB;
while (pointerA !== pointerB) {
  pointerA = pointerA ? pointerA.next : headB;
  pointerB = pointerB ? pointerB.next : headA;
}
return pointerA;

What It Enables

This concept enables fast and memory-efficient detection of where two linked lists merge, unlocking solutions for problems involving shared data paths.

Real Life Example

In social networks, two different friend circles might share common friends. Finding the first common friend where these circles intersect helps in understanding mutual connections and influences.

Key Takeaways

Manual comparison is slow and error-prone.

The intersection point method uses two pointers to find the merge node efficiently.

This technique saves time and memory, making it practical for large linked lists.

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