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

Intersection Point of Two Linked Lists

📖 Scenario: You are working on a social media app where two users have their own friend lists represented as linked lists. Sometimes, these lists share a common friend node, meaning the two lists intersect at some point. Your task is to find the first common friend node where the two lists intersect.

🎯 Goal: Build a program that creates two linked lists with an intersection point, then finds and prints the value at the intersection node.

📋 What You'll Learn

Create two linked lists with some nodes sharing the same reference (intersection).

Use a helper variable to store the length of each linked list.

Implement the logic to find the intersection point of the two linked lists.

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

💡 Why This Matters

🌍 Real World

Finding intersection points in linked lists is useful in social networks, navigation paths, and version control systems where shared nodes represent common points.

💼 Career

Understanding linked list intersections helps in debugging pointer-related bugs and optimizing memory usage in software engineering roles.

1

Create two linked lists with an intersection

Create a linked list node class called ListNode with a constructor that takes value and next. Then create two linked lists: listA with nodes 1 -> 2 -> 3 and listB with nodes 6 -> 3, where the node with value 3 is the same object in both lists (intersection).

DSA Javascript

// Define ListNode class and create two linked lists with intersection
// Your code here

Hint

Start by defining a ListNode class. Then create the shared node with value 3. Use it to build both lists so they share this node.

2

Calculate lengths of both linked lists

Create a function called getLength that takes a linked list head and returns its length. Then create two variables lenA and lenB that store the lengths of listA and listB respectively by calling getLength.

DSA Javascript

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

const intersectNode = new ListNode(3);

const listA = new ListNode(1, new ListNode(2, intersectNode));
const listB = new ListNode(6, intersectNode);

// Create function getLength(head) to return length of linked list
// Then create lenA and lenB to store lengths of listA and listB
// Your code here

Hint

Use a while loop to count nodes until you reach null. Then call this function for both lists.

3

Find the intersection point of the two linked lists

Create a function called getIntersectionNode that takes headA and headB. Use lenA and lenB to advance the longer list's pointer so both pointers are equally far from the end. Then move both pointers step-by-step until they meet or reach null. Return the intersecting node or null if none.

DSA Javascript

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

const intersectNode = new ListNode(3);

const listA = new ListNode(1, new ListNode(2, intersectNode));
const listB = new ListNode(6, intersectNode);

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

const lenA = getLength(listA);
const lenB = getLength(listB);

// Create function getIntersectionNode(headA, headB) to find intersection
// Your code here

Hint

Advance the longer list by the difference in lengths. Then move both pointers together until they meet or reach the end.

4

Print the value at the intersection node

Call getIntersectionNode with listA and listB. Store the result in intersection. Then print the value of intersection if it exists, otherwise print null.

DSA Javascript

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

const intersectNode = new ListNode(3);

const listA = new ListNode(1, new ListNode(2, intersectNode));
const listB = new ListNode(6, intersectNode);

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

const lenA = getLength(listA);
const lenB = getLength(listB);

function getIntersectionNode(headA, headB) {
  let currentA = headA;
  let currentB = headB;

  let diff = Math.abs(lenA - lenB);

  if (lenA > lenB) {
    for (let i = 0; i < diff; i++) {
      currentA = currentA.next;
    }
  } else {
    for (let i = 0; i < diff; i++) {
      currentB = currentB.next;
    }
  }

  while (currentA !== null && currentB !== null) {
    if (currentA === currentB) {
      return currentA;
    }
    currentA = currentA.next;
    currentB = currentB.next;
  }

  return null;
}

// Call getIntersectionNode and print the value or null
// Your code here

Hint

Call the function and print the value if intersection exists, otherwise print null.

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