Intersection Point of Two Linked Lists in DSA Typescript - Build from Scratch

Intersection Point of Two Linked Lists

📖 Scenario: Imagine two train tracks that merge into one at some point. We want to find the exact point where the two tracks join. Here, the tracks are two linked lists, and the joining point is the intersection node.

🎯 Goal: You will build a program to find the intersection point of two singly linked lists. If they intersect, print the value at the intersection node; otherwise, print null.

📋 What You'll Learn

Create two linked lists with some shared nodes to simulate intersection.

Use pointers to traverse both lists.

Implement logic to find the intersection node efficiently.

Print the value of the intersection node or null if no intersection.

💡 Why This Matters

🌍 Real World

Finding the intersection point of linked lists is useful in memory management, detecting shared resources, and debugging pointer-related issues.

💼 Career

Understanding linked list intersections helps in software engineering roles involving data structures, debugging, and optimizing memory usage.

1

Create two linked lists with intersection

Create a class called ListNode with properties val: number and next: ListNode | null. Then create three nodes: shared with value 8, nodeA1 with value 3 pointing to shared, and nodeB1 with value 99 pointing to shared. Finally, create two heads: headA pointing to nodeA1 and headB pointing to nodeB1.

DSA Typescript

// Your code here

Hint

Define a ListNode class with val and next. Create nodes so that both lists share the node with value 8.

2

Set up pointers for traversal

Create two variables pointerA and pointerB and set them to headA and headB respectively.

DSA Typescript

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

const shared = new ListNode(8);
const nodeA1 = new ListNode(3, shared);
const nodeB1 = new ListNode(99, shared);

const headA = nodeA1;
const headB = nodeB1;

// Create pointerA and pointerB variables
// Your code here

Hint

Set pointerA to headA and pointerB to headB to start traversing both lists.

3

Find the intersection node

Use a while loop that continues until pointerA === pointerB. Inside the loop, move pointerA to pointerA.next or to headB if pointerA is null. Similarly, move pointerB to pointerB.next or to headA if pointerB is null.

DSA Typescript

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

const shared = new ListNode(8);
const nodeA1 = new ListNode(3, shared);
const nodeB1 = new ListNode(99, shared);

const headA = nodeA1;
const headB = nodeB1;

let pointerA = headA;
let pointerB = headB;

// Find intersection node using while loop
// Your code here

Hint

Use two pointers that switch heads when reaching the end to find the intersection.

4

Print the intersection node value or null

Print the value of pointerA if it is not null, otherwise print null.

DSA Typescript

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

const shared = new ListNode(8);
const nodeA1 = new ListNode(3, shared);
const nodeB1 = new ListNode(99, shared);

const headA = nodeA1;
const headB = nodeB1;

let pointerA = headA;
let pointerB = headB;

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

// Print the intersection node value or null
// Your code here

Hint

After the loop, pointerA is either the intersection node or null. Print its value 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