Intersection Point of Two Linked Lists in DSA Javascript

Mental Model

Two linked lists may share some nodes at the end, forming an intersection. We want to find the first shared node.

Analogy: Imagine two roads merging into one highway. The point where they join is the intersection point.

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
                      ↑
List B:       9 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: List A: 1->2->3->4->5, List B: 9->4->5 (4 and 5 are shared nodes)

Goal: Find the first node where both lists meet (node with value 4).

Step 1: Calculate lengths of both lists: lenA=5, lenB=3

List A: 1 -> 2 -> 3 -> 4 -> 5 -> null
List B: 9 -> 4 -> 5 -> null

Why: Knowing lengths helps align both lists to compare nodes at the same distance from end

Step 2: Advance pointer in longer list (A) by difference (2 steps)

List A pointer at node 3 -> 4 -> 5 -> null
List B pointer at node 9 -> 4 -> 5 -> null

Why: Align both pointers so they have equal nodes left to traverse

Step 3: Compare nodes at pointers: 3 vs 9 (different), move both forward

List A pointer at 4 -> 5 -> null
List B pointer at 4 -> 5 -> null

Why: Nodes differ, move forward to check next nodes

Step 4: Compare nodes at pointers: 4 vs 4 (same node)

Intersection found at node 4 -> 5 -> null

Why: Same node means intersection point found

Result:

4 -> 5 -> null is the intersection starting point

Annotated Code

DSA Javascript

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

function getLength(head) {
  let length = 0;
  let current = head;
  while (current !== null) {
    length++;
    current = current.next;
  }
  return length;
}

function getIntersectionNode(headA, headB) {
  let lenA = getLength(headA);
  let lenB = getLength(headB);

  // Align start pointers
  while (lenA > lenB) {
    headA = headA.next; // advance longer list pointer
    lenA--;
  }
  while (lenB > lenA) {
    headB = headB.next; // advance longer list pointer
    lenB--;
  }

  // Move both pointers until intersection or end
  while (headA !== null && headB !== null) {
    if (headA === headB) {
      return headA; // intersection found
    }
    headA = headA.next; // advance both pointers
    headB = headB.next;
  }

  return null; // no intersection
}

// Driver code to create lists and test
// Shared nodes
const shared1 = new ListNode(4);
const shared2 = new ListNode(5);
shared1.next = shared2;

// List A: 1->2->3->4->5
const headA = new ListNode(1);
headA.next = new ListNode(2);
headA.next.next = new ListNode(3);
headA.next.next.next = shared1;

// List B: 9->4->5
const headB = new ListNode(9);
headB.next = shared1;

const intersection = getIntersectionNode(headA, headB);
if (intersection !== null) {
  let curr = intersection;
  let result = '';
  while (curr !== null) {
    result += curr.val + ' -> ';
    curr = curr.next;
  }
  result += 'null';
  console.log(result);
} else {
  console.log('No intersection');
}

while (lenA > lenB) { headA = headA.next; // advance longer list pointer lenA--; }

advance pointer in longer list to align both lists

while (lenB > lenA) { headB = headB.next; // advance longer list pointer lenB--; }

advance pointer in longer list to align both lists

while (headA !== null && headB !== null) { if (headA === headB) { return headA; // intersection found } headA = headA.next; // advance both pointers headB = headB.next; }

move both pointers forward together until intersection or end

Output

4 -> 5 -> null

Complexity Analysis

Time: O(m + n) because we traverse both lists to get lengths and then traverse aligned parts once

Space: O(1) because we use only pointers and counters, no extra data structures

vs Alternative: Naive approach compares every node of one list with every node of the other, O(m*n), much slower

Edge Cases

One or both lists are empty

Returns null immediately, no intersection

DSA Javascript

while (current !== null) { length++; current = current.next; }

Lists do not intersect

Returns null after traversing both lists

DSA Javascript

return null; // no intersection

Intersection at head node

Returns head node as intersection

DSA Javascript

if (headA === headB) { return headA; }

When to Use This Pattern

When you see two linked lists and need to find if they share nodes, use the intersection pattern by aligning lengths and moving pointers together.

Common Mistakes

Mistake: Comparing node values instead of node references to find intersection
Fix: Compare nodes by reference (headA === headB), not by value

Mistake: Not aligning the longer list pointer before simultaneous traversal
Fix: Calculate lengths and advance the longer list pointer by the difference first

Summary

Finds the first shared node where two linked lists intersect.

Use when two linked lists may share nodes and you want to find the joining point.

Align both lists by length, then move pointers together to find the intersection.

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