Проверка, является ли связанный список палиндромом - Чего мне здесь не хватает? - PullRequest
Новая
       10

Проверка, является ли связанный список палиндромом - Чего мне здесь не хватает?

0 голосов
/ 01 ноября 2018

Вот моя попытка решения проблемы. 

 public boolean isPalindrome(ListNode head) {

    if(head == null || head.next == null)
        return true;
    ListNode hare = head;
    ListNode tort = head;
    while(hare!=null && hare.next!=null) {
        //System.out.print("Hare "+ hare.val +"tort  "+tort.val);
        hare = hare.next.next;
        tort = tort.next;
    }
    //Tort is the middle of the list
    reverseLL(tort);
    ListNode tmp = tort;
    printList(tmp);
    while(tort!=null) {
        if(head.val!=tort.val)
            return false;
        head = head.next;
        tort = tort.next;
        continue;
    }
    return true;
}

private ListNode reverseLL(ListNode head) {
    if(head == null || head.next == null) {
        return head;
    }
    ListNode nextElem = head.next;
    //System.out.println("Processing "+head.val);

    head.next = null;
    ListNode rev = reverseLL(nextElem);
    nextElem.next = head;
    return rev;
}

 private void printList(ListNode head){
        while(head!=null){
            System.out.println("[" +head.val + "]");
            head = head.next;
        }

    }

Но я заметил кое-что довольно странное, что я не смог понять. tort в настоящее время заканчивается в середине связанного списка. Тем не менее, изменение от tort до конца, кажется, разъединяет правонарушение от остальной части связанного списка.

Например, если введено значение 1-> 2-> 3-> 4, то в конечном итоге деликт равен 3, но после распечатки списка после обращения к деликту печатается только 3, т.е. 3 отключен от остальной части списка.

Я тестировал это reverseLL отдельно, и оно работает, но когда оно применяется как часть метода isPalindrome. Есть идеи, что мне не хватает?

Ответы [ 2 ]

0 голосов
/ 01 ноября 2018

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

  1. Инициализация стека
  2. Пройдите по списку и поместите каждый элемент на вершину стека

  3. Пока стек не пуст:

    1. Хлопните голову в стеке
    2. Сравните всплывающий элемент с заголовком списка
    3. Если неравенство, вернуть false
    4. Вставьте другой элемент, переместите один элемент вперед в списке

  4. возврат true

Вот реализация Java с обобщениями: 

    public <T> boolean isPalindrome(ListNode<T> head) {
        Stack<ListNode<T>> stack = new Stack<>();
        ListNode<T> x = head;
        while(x != null) {
            stack.push(x);
            x = x.next;
        }
        while(!stack.isEmpty()) {
            ListNode<T> el = stack.pop();
            if(el.t != head.t) return false;
            head = head.next;
        }
        return true;
    }

Этот алгоритм O (n) во времени и O (n) в пространстве.

0 голосов
/ 01 ноября 2018

Когда вы находите середину связанного списка в первом цикле while, почему бы вам не сохранить указатель на узел, предшествующий tort: ​​

ListNode prev_tort = head;
while(hare!=null && hare.next!=null) {
    //System.out.print("Hare "+ hare.val +"tort  "+tort.val);
    hare = hare.next.next;
    prev_tort = tort;
    tort = tort.next;
}

Теперь, когда есть четное количество элементов, заяц будет NULL. Итак, для нечетного случая пропустите средний узел: 

if(hare != NULL){
     tort = tort.next;
     prev_tort = prev_tort.next;
}
tort = reverseLL(tort);
prev_tort.next = tort;  // only to ensure list is connected

, а затем приходит ваш код сравнения.

Также в функции reverseLL (): 

ListNode rev = reverseLL(nextElem);
head.next.next = head;
head.next = NULL;

return rev;

Если я правильно понимаю, вы пытаетесь проверить, является ли список палиндромом, перевернув вторую половину. В этом случае, для ввода 1-> 2-> 3-> 4, не должен ли деликтный указатель на 4 после изменения второй половины? Это то, что делает приведенный выше код (и список будет: 1-> 2-> 4-> 3).

...