Не удается пройти все тестовые случаи для вопроса LeetCode, чтобы найти пересечение двух связанных списков с использованием карты хеша - PullRequest
Новая
       41

Не удается пройти все тестовые случаи для вопроса LeetCode, чтобы найти пересечение двух связанных списков с использованием карты хеша

0 голосов
/ 25 декабря 2018

Я прошел первоначальный тестовый пример, но он показывает неправильный ответ для тестового примера. (Связанные списки приведены в тестовом примере: [0,9,1,2,4] и [3,2,4]. Ожидаемыйответ - это узел со значением 2, но я получаю 4.) Может ли кто-нибудь заметить ошибку в коде?

Другие способы решения проблемы приветствуются, но я хотел сделать это с помощью Hash map для моей собственной практики. 

class Solution{
    public:
            ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
                    unordered_map<int, ListNode*> map;
                    int i=0;
                    while(headA!=NULL){ //inserting all nodes of LL A in hash map
                            map[i]=headA;
                            headA=headA->next;
                            i++;
                    }

                    while(1){
                            for (auto it = map.begin(); it != map.end(); it++) {
                                    if (it->second == headB){
                                            return it->second;
                                    }
                                    else{
                                            if(headB->next!=NULL) {
                                                    headB=headB->next;
                                            }
                                            else{
                                                    break;
                                            }
                                    }
                            }
                    }
                    return NULL;
            }
};

1 Ответ

0 голосов
/ 25 декабря 2018

Я бы хотел предвосхитить это, сказав, что unordered_map не имеет гарантий порядка хранения.Это означает, что элементы не обязательно хранятся в том же порядке, в котором они были вставлены.
Давайте посмотрим на соответствующий код. 

while(1){
      for (auto it = map.begin(); it != map.end(); it++) {
          if (it->second == headB){
              return it->second;
          }
          else{
              if(headB->next!=NULL) {
                  headB=headB->next;
              }
              else{
                  break;
              }
          }
}

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

  • Если случайный порядок, по которому итератор проходит по карте, имеет значениеэто соответствует соответствующему значению headB.
  • Если headB достигнет своего последнего значения, не найдя соответствия, while(1) перезапустит внутренний цикл for и сравнит первое значение, на которое указывает итератор, с последним значением в связанном headBсписок.Если это сравнение выполнится успешно, программа вернется.В противном случае цикл продолжается вечно.
...