Блог

Как многие знают, вышеупомянутая проблема довольно классическая для связанных списков. Я пытался решить эту проблему в leetcode, используя метод хеширования (зная другое более оптимальное решение), но он не проходит все тестовые примеры (41/46). Я не знаю, какой случай я не рассматриваю. любая помощь приветствуется.

     def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    s = set()
    list1 = headA
    list2 = headB
    while (not list1) or (not list2):
        return None
    
    while list1 and list1.next:
        s.add(list1)
        list1 = list1.next
        
        
    while list2 and list2.next:
        if list2 in s:
            return list2
        list2 = list2.next
        
    return None
  

Вам нужно изменить while list1 and list1.next: на while list1: и while list2 and list2.next: на while list2: .

Пример, который не работает в вашем случае:

Список 1: 1-> 5

Список 2: 2-> 5

В вашем коде для списка 1 в set будет вставлено 1, но не 5. В списке 2, 2 будет проверяться в наборе, но не 5.

Кроме того, это должно завершиться неудачей.

Список 1: 1-> 5

Список 2: 5

Таким образом, вы можете получить другие неудачные тестовые примеры.

Мы также можем решить эту проблему, просто немного без формулировок:

 class Solution:
    def getIntersectionNode(self, la, lb):
        if not la or not lb:
            return 
        a, b = la, lb
        while a and b and a != b:
            a, b = a.next, b.next
            if a == b:
                return b
            if not a:
                a = lb
            if not b:
                b = la
        return a