Связанный список палиндрома - PullRequest
Новая
       31

Связанный список палиндрома

0 голосов
/ 09 июня 2018

Учитывая односвязный список, я хочу определить, является ли это палиндромом.Для моего метода я решил повернуть вспять первую половину связанного списка, а затем сравнить, имеют ли две половины связанного списка эквивалентные элементы.Ранее я поместил строку fast = fast.next.next в конце первого цикла while (ниже 4 других строк).Однако когда я это сделал, я получил исключение Null Pointer.Теперь, когда я перемещаю его на первую строку в цикле while, я не получаю ошибок, и моя программа принята.Может кто-нибудь объяснить мне, почему это так?Спасибо!Ниже мой код: 

class Solution {
    public boolean isPalindrome(ListNode head) {

        if(head == null || head.next == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            ListNode temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;

        }

        if(fast != null){
            slow = slow.next;
        }

        while(prev != null && prev.val == slow.val){
            prev = prev.next;
            slow = slow.next;
        }

        return slow == null;
    }
}

1 Ответ

0 голосов
/ 09 июня 2018

Это потому, что если вы сначала позвоните slow.next = prev, вы потеряете ссылку на то, что будет first.next.next.Почему это так?

Для ваших инициализаций: 

fast -> head
slow -> head
prev -> null

Теперь в вашем цикле while вы проверяете, не указывает ли fast.next на null.Следовательно, fast.next.next является действительным.Однако обратите внимание, что slow.next указывает на ту же ссылку, что и fast.next.Для объяснения мы скажем, что оба они указывают на адрес памяти, называемый SOMETHING. 

fast (HEAD) -> next -> SOMETHING
slow (HEAD) -> next -> SOMETHING

ЕСЛИ вы положите fast.next.next на вершину цикла while, это допустимо, потому что этовсе еще указывает на что-то.

Если вы поместите fast.next.next внизу цикла while, тогда строка slow.next = prev сначала установит head.next как null.

Вы теперь изменили head.next, чтобы указать ни на что.Поскольку fast также указывал на голову, fast.next теперь также указывает на ноль. 

fast (head) -> next -> NULL

Поэтому вызов fast.next.next вызовет исключение нулевой ссылки.

Hopeэто помогает.

...