Блог

Я понимаю другие подходы, такие как использование стека и изменение второй половины связанного списка. Но что не так с моим подходом?

 * Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
   public boolean isPalindrome(ListNode head) {
       if(head.next==null){return true;}
       
       while(head!=null){
           ListNode ptr=head, preptr=head;
           while(ptr.next!=null){ptr=ptr.next;}
           if(ptr==head){break;}
           while(preptr.next.next!=null){preptr=preptr.next;}
           
           if(head.val==ptr.val){
               preptr.next=null;
               head=head.next;
           }
           else{return false;}   
       }
       
       return true;
       
   }
}```
 

О вашем решении можно сказать следующее:

• Он завершается неудачей с исключением, если head это null так . Чтобы избежать этого, вы можете просто удалить первое if утверждение. Этот случай не нуждается в отдельной обработке. Если список состоит из одного узла, то первая итерация выполнит break и, таким образом, вы получите true возвращаемое значение. Но, по крайней мере, вы не получите доступ ->next , когда head это null
• Это изменяет данный список. Это не очень приятно. Вызывающий абонент не ожидает, что это произойдет, и может потребоваться исходный список для других целей даже после этого вызова isPalindrome .
• Это происходит медленно. Его временная сложность квадратична. Если это часть задачи кодирования, то тестовые данные могут быть большими, и выполнение вашей функции может превысить отведенное время.

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

Вы можете сделать это, используя только следующий список:

1. Подсчитайте количество узлов в списке
2. Используйте это для идентификации первого узла второй половины списка. Если число узлов нечетное, пусть это будет узел после центрального узла.
3. Примените алгоритм изменения списка к этой второй половине. Теперь у вас есть два более коротких списка.
4. Сравните, что значения в этих двух списках равны (игнорируйте центральный узел, если он был). Запомните результат (ложный или истинный)
5. Повторите шаг 3, чтобы отмена была отменена, и список вернулся в исходное состояние.
6. Верните результат, найденный на шаге 4.

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