Где пересекаются два связанных списка?

Решение проблем со структурой данных может быть сложным для новичка. Смотришь на проблему и возникает вопрос: с чего начать? Недавно я решал задачу поиска пересечения двух связанных списков. Проанализировав проблему, я нашел решение, которое я объясню ниже.

Задача

Ваша задача — написать программу для поиска узла, в котором начинается пересечение двух односвязных списков. Вы не можете изменять исходный ввод (предположим, что в списке нет цикла).

Одно из возможных решений — просмотреть первый список и запомнить все узлы, которые вы посетили. Вы можете использовать структуру Set() для хранения узлов по мере их посещения. Затем просмотрите второй список и для каждого узла проверьте, есть ли он в наборе. Если проверка положительная, это начало пересечения списков.

//node function Node(value) {
//   this.value = value;
//   this.next = null;
//}
//Time complexity: linear 
//Memory complexity: linear 
const findIntersectionNode = function(headA, headB) {
  let currentHeadA = headA
  let currentHeadB = headB
  let mySet = new Set()
  while (currentHeadA !== null) {
    mySet.add(currentHeadA)
    currentHeadA = currentHeadA.next
}
  while (currentHeadB !== null) {
    if (mySet.has(currentHeadB)) { 
      return currentHeadB
}
  currentHeadB = currentHeadB.next
}
  return null
}