Различные подходы к решению Leetcode 160 в JavaScript

Одной из распространенных проблем, связанных со связанными списками, является определение того, пересекаются ли и где два списка. Точка пересечения определяется как узел, в котором два связанных списка имеют общие элементы. Эта проблема представляет собой интересную проблему из-за разной длины списков и необходимости эффективно идентифицировать точку пересечения.

В этой статье мы рассмотрим различные подходы к решению проблемы точки пересечения, реализуем их в javascript и обсудим их соответствующие временные и пространственные сложности.

Постановка проблемы:

Учитывая заголовки двух односвязных списков headA и headB, вернуть узел, в котором два списка пересекаются. Если два связанных списка вообще не пересекаются, вернуть null.

Подход 1: грубая сила

Один простой подход заключается в сравнении каждого узла первого связанного списка с каждым узлом второго связанного списка. Если узел в первом связанном списке совпадает с любым узлом во втором связанном списке, это точка пересечения.

  1. В качестве входных данных функция будет принимать два связанных списка.
  2. Используйте два вложенных цикла для сравнения значений узла на каждой итерации в обоих связанных списках.
  3. Если пересечение найдено, верните этот узел. В противном случае вернуть ноль.
// ES6 Arrow Function
const getIntersectionNode = (headA, headB) => {
    let ha = headA;

    while(ha !== null) {
        let hb = headB;
        while(hb !== null) {
            if(ha === hb) return ha;
            hb = hb.next;
        }
        ha = ha.next;
    }

    // No intersection found
    return null;
}

Временная сложность:O(N * M)

Мы итерируем первый связанный список длины N и для каждого узла мы итерируем второй связанный список длины M. Наихудший сценарий возникает, когда нет пересечения, и нам нужно сравнить каждый узел первого связанного списка. список с каждым узлом второго связанного списка.

Пространственная сложность:O(1)

В этом подходе используется постоянное пространство, поскольку для решения проблемы не требуются дополнительные структуры данных.

Подход 2: набор хэшей

  1. В этом подходе мы можем использовать набор хэшей для хранения адресов памяти узлов в первом связанном списке.
  2. Затем мы проходим по второму связанному списку и проверяем, существует ли адрес памяти какого-либо узла в хеш-наборе.
  3. Если мы находим совпадение, это точка пересечения. В противном случае вернуть ноль.
// ES6 Arrow Function
const getIntersectionNode = (headA, headB) => {
    let set = new Set();

    let ha = headA;
    while(ha !== null) {
        set.add(ha);
        ha = ha.next;
    }

    let hb = headB;
    while(hb !== null) {
        if(set.has(hb)) return hb;
        hb = hb.next;
    }

    return null;
}

Временная сложность:O(N + M)

Мы перебираем первый связанный список длины N, чтобы сохранить адреса памяти его узлов в хеш-наборе. Затем мы перебираем второй связанный список длины M, чтобы проверить, существует ли адрес памяти какого-либо узла в хеш-наборе. Обе итерации являются линейными. Следовательно, временная сложность линейна.

Пространственная сложность:O(N)

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

Подход 3: два указателя

  1. Во-первых, мы находим длины обоих связанных списков.
  2. Затем мы перемещаем указатель более длинного связанного списка вперед на разницу в длине. Эта корректировка гарантирует, что оба указателя начинаются с одной и той же относительной позиции от точки пересечения.
  3. После корректировки указателей мы проходим по обоим связанным спискам одновременно, перемещая указатели по одному узлу за раз.
  4. Во время каждой итерации мы сравниваем узлы, на которые указывают два указателя.
  5. Если мы находим соответствующий узел, это точка пересечения.
  6. Если мы достигнем конца обоих связанных списков, не найдя пересечения, то пересечения нет, и мы вернем null.
// ES6 Arrow Function
const getIntersectionNode = (headA, headB) => {
    let ha = headA, hb = headB;

    // Find the length of both linked lists
    let lenA = getLength(ha);
    let lenB = getLength(hb);

    // Adjust the pointer to make them start at the same relative position from the intersection point
    while(lenA > lenB) {
        ha = ha.next;
        lenA--;
    }

    while(lenB > lenA) {
        hb = hb.next;
        lenB--;
    }

    // Traverse both the linked lists simultaneously util the intersection point is found
    while(ha !== hb) {
        ha = ha.next;
        hb = hb.next;
    }

    // Intersection node or null (if no intersection is found)
    return ha;
}

const getLength = node => {
    let len = 0; 
    while(node !== null) {
        len++;
        node = node.next;
    }
    return len;
}

Временная сложность:O(N + M)

Сначала мы находим длины обоих связанных списков, что занимает O(N + M) времени, так как нам нужно пройти по каждому списку один раз. Затем настройка указателей, чтобы они начинались с одной и той же относительной позиции, занимает постоянное время. Наконец, итерация по обоим связанным спискам одновременно занимает время O(N + M) в худшем случае, поскольку мы проходим до тех пор, пока не найдем точку пересечения или не достигнем конца обоих списков.

Пространственная сложность:O(1)

Независимо от размера связанных списков сложность пространства остается постоянной.

И вот оно, ребята! Мы исследовали различные подходы, оптимизировали наши решения и, надеюсь, повеселились. Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!

Проблема - Литкод 160