Intersection Point of Two Linked Lists in DSA Javascript - 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

Traverse both lists with two pointers; when one reaches end, switch to the other list's head. They meet at intersection or both become null.

Execution Sample

DSA Javascript

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 singly linked lists intersect by traversing both with two pointers.

Execution Table

Step	Operation	pointerA Node	pointerB Node	Visual State	Pointer Changes
1	Initialize pointers	A1	B1	ListA: A1 -> A2 -> C1 -> C2 -> C3 ListB: B1 -> B2 -> B3 -> C1 -> C2 -> C3	pointerA = A1, pointerB = B1
2	Compare pointerA and pointerB	A1	B1	No match	Move pointerA to A2, pointerB to B2
3	Compare pointerA and pointerB	A2	B2	No match	Move pointerA to C1, pointerB to B3
4	Compare pointerA and pointerB	C1	B3	No match	Move pointerA to C2, pointerB to C1
5	Compare pointerA and pointerB	C2	C1	No match	Move pointerA to C3, pointerB to C2
6	Compare pointerA and pointerB	C3	C2	No match	Move pointerA to null, pointerB to C3
7	pointerA reached end, switch to headB	null	C3	pointerA switches to B1	pointerA = B1, pointerB moves to null
8	pointerB reached end, switch to headA	B1	null	pointerB switches to A1	pointerA moves to B2, pointerB = A1
9	Compare pointerA and pointerB	B2	A1	No match	Move pointerA to B3, pointerB to A2
10	Compare pointerA and pointerB	B3	A2	No match	Move pointerA to C1, pointerB to C1
11	Compare pointerA and pointerB	C1	C1	Match found	Intersection at C1
12	Return intersection node	C1	C1	End	Return C1

💡 Pointers meet at node C1, the intersection point.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	Final
pointerA	A1	A2	C1	null	B1	B3	C1
pointerB	B1	B2	B3	C3	null	A2	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 both pointers traverse equal total lengths, allowing them to meet at the intersection if it exists (see step 7 in execution_table).

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

We compare nodes by reference (pointer equality) because intersection means the exact same node object, not just equal values (see steps 2-11 in execution_table).

What happens if the lists do not intersect?

Both pointers will eventually become null after traversing both lists fully, causing the loop to exit with no intersection (not shown here but implied by exit condition).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is pointerA pointing to?

A null

B C3

C B1

D C2

💡 Hint

Check the 'pointerA Node' column at step 6 in execution_table.

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

A Step 11

B Step 10

C Step 4

D Step 12

💡 Hint

Look for 'Match found' in the 'Operation' column in execution_table.

If pointerB did not switch to headA at step 8, what would happen?

A The pointers would meet at the last node.

B The pointers would meet earlier.

C The pointers would never meet even if intersection exists.

D The pointers would meet at the first node.

💡 Hint

Refer to the concept_flow and step 8 in execution_table about switching pointers.

Concept Snapshot

Intersection Point of Two Linked Lists:
- Use two pointers starting at each list head.
- Move pointers forward; when reaching end, switch to other list's head.
- Pointers meet at intersection or both become null.
- Compare nodes by reference, not value.
- Time complexity: O(m+n), space: O(1).

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 key is comparing nodes by reference, not by value, because intersection means the exact same node object. This method runs in linear time and uses constant extra space.

Practice

1. What does the term Intersection Point of Two Linked Lists mean?

easy

A. The node where two linked lists merge and share the same next nodes

B. The first node of the longer linked list

C. The last node of the shorter linked list

D. The node with the highest value in both lists

Solution

1. Step 1: Understand linked list structure

   Linked lists are chains of nodes where each node points to the next node.

2. Step 2: Define intersection point

   The intersection point is where two lists share the exact same node object, meaning from that node onward, both lists are identical.

3. Final Answer:

   The node where two linked lists merge and share the same next nodes -> Option A

4. Quick Check:

   Intersection means shared node = D [OK]

Hint: Intersection means shared node reference, not just value [OK]

Common Mistakes:

• Thinking intersection means same value, not same node
• Confusing intersection with concatenation
• Assuming intersection is always at head

2. Which of the following JavaScript code snippets correctly initializes two linked lists that intersect at node with value 8?

easy

A. const list1 = { val: 3, next: { val: 8, next: null } };
const list2 = { val: 7, next: { val: 8, next: null } };

B. const intersectNode = { val: 8, next: null };
const list1 = { val: 3, next: intersectNode };
const list2 = { val: 7, next: intersectNode };

C. const list1 = { val: 3, next: null };
const list2 = { val: 7, next: null };

D. const intersectNode = { val: 8, next: null };
const list1 = { val: 3, next: { val: 8, next: null } };
const list2 = { val: 7, next: intersectNode };

Solution

1. Step 1: Check for shared node reference

   const intersectNode = { val: 8, next: null }; const list1 = { val: 3, next: intersectNode }; const list2 = { val: 7, next: intersectNode }; creates one node object for value 8 and both lists point to it, ensuring intersection.

2. Step 2: Compare other options

   const list1 = { val: 3, next: { val: 8, next: null } }; const list2 = { val: 7, next: { val: 8, next: null } }; creates two separate nodes with value 8, no intersection. const list1 = { val: 3, next: null }; const list2 = { val: 7, next: null }; has no intersection node. const intersectNode = { val: 8, next: null }; const list1 = { val: 3, next: { val: 8, next: null } }; const list2 = { val: 7, next: intersectNode }; has list1 pointing to a new node, not the shared one.

3. Final Answer:

   shares the same node object for intersection -> Option B

4. Quick Check:

   Shared node object = A [OK]

Hint: Intersection requires same node object, not just same value [OK]

Common Mistakes:

• Creating separate nodes with same value instead of shared node
• Not linking both lists to the intersecting node
• Confusing node value with node reference

3. Given the following code, what will be the output of console.log(getIntersectionNode(listA, listB)?.val || null);?

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

const intersect = { val: 5, next: { val: 6, next: null } };
const listA = { val: 1, next: { val: 2, next: intersect } };
const listB = { val: 9, next: { val: 4, next: intersect } };

medium

A. 5

B. null

C. 6

D. 1

Solution

1. Step 1: Understand the algorithm

   The function uses two pointers that traverse both lists; when they meet, that node is the intersection.

2. Step 2: Identify intersection node

   Both lists share the node with value 5, so the function returns that node.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Intersection node value = 5 [OK]

Hint: Two-pointer method returns intersection node or null [OK]

Common Mistakes:

• Expecting value 6 instead of 5
• Confusing node value with list head value
• Not understanding pointer switching logic

4. The following code attempts to find the intersection node of two linked lists but may cause infinite loop when there is no intersection. What is the bug?

function getIntersectionNode(headA, headB) {
  let a = headA, b = headB;
  while (a !== b) {
    a = a.next || headB;
    b = b.next || headA;
  }
  return a;
}

medium

A. The function should return b instead of a

B. The loop condition should be 'while(a && b && a !== b)'

C. The pointers should not switch lists

D. Using 'a.next || headB' incorrectly jumps to headB when a.next is null

Solution

1. Step 1: Analyze pointer update logic

   Using 'a.next || headB' sets a to headB when a.next is null (while a points to last node), skipping null handling and causing infinite loops when no intersection.

2. Step 2: Correct pointer switching

   The correct approach is to check if 'a' is null, then switch to headB; otherwise, move to a.next.

3. Final Answer:

   Using 'a.next || headB' causes skipping headB when a.next is null -> Option D

4. Quick Check:

   Pointer update must check 'a' null, not 'a.next' [OK]

Hint: Check pointer null before moving to next list head [OK]

Common Mistakes:

• Using 'a.next || headB' instead of 'a ? a.next : headB'
• Not handling null pointers correctly
• Returning wrong pointer at end

5. You have two singly linked lists that intersect. List A length is 7, List B length is 5. How can you find the intersection point efficiently?

hard

A. Reverse both lists and compare from the start

B. Traverse both lists fully and compare node values to find intersection

C. Advance the longer list by difference in lengths, then move both pointers together until they meet

D. Use a hash set to store all values of the shorter list, then check values of the longer list

Solution

1. Step 1: Calculate length difference

   Find lengths of both lists; difference is 2 (7 - 5).

2. Step 2: Advance longer list pointer

   Move pointer of longer list ahead by 2 nodes to align both lists equally from intersection point.

3. Step 3: Move both pointers together

   Traverse both lists simultaneously until pointers are equal, which is the intersection node.

4. Final Answer:

   Advance longer list by difference in lengths, then move both pointers together until they meet -> Option C

5. Quick Check:

   Align pointers by length difference = A [OK]

Hint: Align list starts by length difference before simultaneous traversal [OK]

Common Mistakes:

• Comparing node values instead of node references
• Not aligning pointers before traversal
• Using extra space unnecessarily