Блог

Главная - Вопросы по программированию - Я создал этот код, чтобы выяснить, является ли данный связанный список палиндромом. это не работает в случае [1,1,2,1]

Я создал этот код, чтобы выяснить, является ли данный связанный список палиндромом. это не работает в случае [1,1,2,1]

#c 11 #c 14

Вопрос:

Я переворачиваю( reverse ) связанный список и сравниваю его с исходным списком, если оба они равны. Это палиндром, иначе это не так.

    void reverse(ListNode *amp;N)     //reversing the copy of linked list
      {
         ListNode *one,*two,*three;
         one=N;
         two=N;
         three=NULL;
         while(one)
         {
            one=one->next;
            two->next= three;
            three=two;
            two=one;

          }
             N=three;
        }

    bool isPalindrome(ListNode* head)
    {
        ListNode* rev = head;
        ListNode *temp=head;
        reverse(rev);
        while(temp)                         //checking if reverse and original are equal
        {
            if(rev->val!= temp->val)return false;
            rev=rev->next;
            temp=temp->next;
        }
        return true;
    }
```C

Комментарии:

1. Ваш комментарий //reversing the copy of linked list неверен. Список никогда не копируется; вы просто создаете копию первого узла, которая содержит копию указателя на второй узел (но это не копия второго узла; просто копия указателя). Когда он перевернут, вы переворачиваете весь исходный список, а затем сравниваете его с самим собой; и, конечно, он совпадает. Я бы посоветовал попытаться сделать это без копирования или изменения списка; перейдите к концу, а затем сравните движение вперед и назад одновременно. Если это не двусвязный список, рассмотрите использование стека.

2. Большое спасибо, брат.

Метки: , , , ,