Intersection Point of Two Linked Lists in DSA Typescript - Execution Trace

Concept Flow - Intersection Point of Two Linked Lists

Start at headA and headB

↓

Traverse both lists simultaneously

↓

If pointerA reaches end, switch to headB

↓

If pointerB reaches end, switch to headA

↓

Compare pointerA and pointerB

Yes No↓

Intersection

↓

Repeat until intersection or both null

Start two pointers at heads of both lists. Move them forward. When one reaches end, switch to other list's head. Continue until pointers meet or both reach null.

Execution Sample

DSA Typescript

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

Finds the node where two linked lists intersect by switching pointers between lists when reaching the end.

Execution Table

Step	Operation	PointerA Node	PointerB Node	PointerA Switch	PointerB Switch	Visual State
1	Start	A1	B1	No	No	ListA: A1 -> A2 -> C1 -> C2 -> C3 ListB: B1 -> B2 -> B3 -> C1 -> C2 -> C3
2	Move pointers forward	A2	B2	No	No	PointerA at A2, PointerB at B2
3	Move pointers forward	C1	B3	No	No	PointerA at C1, PointerB at B3
4	Move pointers forward	C2	C1	No	No	PointerA at C2, PointerB at C1
5	Move pointers forward	C3	C2	No	No	PointerA at C3, PointerB at C2
6	Move pointers forward	null	C3	Yes (to headB)	No	PointerA reached end, switches to headB; PointerB at C3
7	Move pointers forward	B1	null	No	Yes (to headA)	PointerA at B1; PointerB reached end, switches to headA
8	Move pointers forward	B2	A1	No	No	PointerA at B2; PointerB at A1
9	Move pointers forward	B3	A2	No	No	PointerA at B3; PointerB at A2
10	Move pointers forward	C1	C1	No	No	PointerA and PointerB meet at C1 (intersection)
11	Return intersection	C1	C1	No	No	Intersection found at node C1

💡 Pointers meet at node C1, the intersection point.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
pointerA	A1	A2	C1	C2	C3	null	B1	B2	B3	C1	C1	C1
pointerB	B1	B2	B3	C1	C2	C3	null	A1	A2	A1	C1	C1

Key Moments - 3 Insights

Why do we switch pointerA to headB when it reaches the end of list A?

Switching pointerA to headB ensures it traverses list B after finishing list A, allowing both pointers to cover equal total lengths. This is shown in step 6 of the execution_table.

What happens if the lists do not intersect?

Both pointers will eventually become null after traversing both lists fully without meeting. The loop ends when pointerA === pointerB === null, meaning no intersection.

Why do we compare pointerA and pointerB directly instead of their values?

We compare nodes (references) because intersection means the exact same node object, not just equal values. This is why in step 10, pointers meeting means intersection.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what happens to pointerA?

A It switches to headB because it reached the end of list A

B It moves to the next node in list A

C It becomes null and stops

D It switches to headA again

💡 Hint

Check the 'PointerA Switch' column at step 6 in execution_table

At which step do pointerA and pointerB first point to the same node?

A Step 5

B Step 10

C Step 7

D Step 3

💡 Hint

Look at the 'PointerA Node' and 'PointerB Node' columns to find when they match

If list B was shorter and intersected earlier, how would the execution_table change?

A Pointers would meet at an earlier step

B PointerA would never switch to headB

C PointerB would become null immediately

D The loop would never end

💡 Hint

Consider how the meeting point depends on list lengths and pointer movements

Concept Snapshot

Intersection Point of Two Linked Lists:
- Use two pointers starting at each list head.
- Move pointers forward one node at a time.
- When a pointer reaches list end, switch it to the other list's head.
- Continue until pointers meet or both become null.
- Meeting node is the intersection point or null if none.

Full Transcript

This concept finds the intersection node of two singly linked lists by using two pointers. Each pointer starts at the head of one list. They move forward one node at a time. When a pointer reaches the end of its list, it switches to the head of the other list. This way, both pointers traverse the combined length of both lists. If the lists intersect, the pointers will meet at the intersection node. If not, both pointers will become null, ending the search. The execution table shows each step with pointer positions and switches. Key moments clarify why pointers switch lists and why node references are compared. The visual quiz tests understanding of pointer switching, meeting steps, and effects of list length changes.

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