160. Intersection of Two Linked Lists

leetcode easy

#csharp#dynamic-programming#easy#hash-table#leetcode#linked-list#string

Task

Даны головы двух односвязных списков headA и headB. Верните узел, в котором эти два списка пересекаются. Если два связанных списка не имеют пересечений, верните null.

Например, следующие два связанных списка начинают пересекаться в узле c1.

Пример:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output: Intersected at '8'

Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).

From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

C# solution

matched/original

public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> nodesInB = new HashSet<ListNode>();
        while (headB != null) {
            nodesInB.Add(headB);
            headB = headB.next;
        }
        while (headA != null) {
            if (nodesInB.Contains(headA)) {
                return headA;
            }
            headA = headA.next;
        }
        return null;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> nodesInB = new HashSet<ListNode>();
        while (headB != null) {
            nodesInB.push_back(headB);
            headB = headB.next;
        }
        while (headA != null) {
            if (nodesInB.Contains(headA)) {
                return headA;
            }
            headA = headA.next;
        }
        return null;
    }
}

Java solution

matched/original

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nodesInB = new HashSet<ListNode>();

        while (headB != null) {
            nodesInB.add(headB);
            headB = headB.next;
        }

        while (headA != null) {
            if (nodesInB.contains(headA)) {
                return headA;
            }
            headA = headA.next;
        }

        return null;
    }
}

JavaScript solution

matched/original

var getIntersectionNode = function (headA, headB) {
    let nodesInB = new Set();

    while (headB !== null) {
        nodesInB.add(headB);
        headB = headB.next;
    }

    while (headA !== null) {
        if (nodesInB.has(headA)) {
            return headA;
        }
        headA = headA.next;
    }

    return null;
};

Python solution

matched/original

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        while headA is not None:
            pB = headB
            while pB is not None:
                if headA == pB:
                    return headA
                pB = pB.next
            headA = headA.next

        return None

Go solution

matched/original

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    nodesInB := make(map[*ListNode]bool)

    for headB != nil {
        nodesInB[headB] = true
        headB = headB.Next
    }

    for headA != nil {
        if _, exist := nodesInB[headA]; exist {
            return headA
        }
        headA = headA.Next
    }

    return nil
}

Explanation

Algorithm

1️⃣

Сохранение ссылок из списка B:

Проходим по всем узлам списка B и сохраняем ссылки (адреса) каждого узла в хеш-таблицу. Это позволит нам быстро проверять, содержится ли узел из списка A в списке B.

2️⃣

Проверка узлов списка A:

Далее, для каждого узла из списка A проверяем, существует ли такой узел в хеш-таблице, созданной на предыдущем шаге. Если такой узел найден, то он является точкой пересечения, и мы возвращаем этот узел.

3️⃣

Обработка отсутствия пересечения:

Если до конца списка A не найдено ни одного узла, который бы совпал с узлами из хеш-таблицы, возвращаем null, указывая на отсутствие пересечения между списками.

😎