Java, функция не распознает операторы возврата - PullRequest
Новая
       10

Java, функция не распознает операторы возврата

2 голосов
/ 04 февраля 2020

При написании кода для проверки, является ли связанный список паллиндромом или нет, я создал функцию reverseLL, которая возвращает обратный связанный список, и функцию isPallindrome для проверки. Проблема в том, что оператор return внутри l oop не обнаруживается и только последнее утверждение, которое возвращает истину; выполняется каждый раз: я проверяю, является ли LL паллиндромом, разделяя его на 2 части и обращая вторую половину, затем сравнивая обе половины 

public static Node<Integer> reverseLL(Node<Integer> head){
    Node<Integer> prev = null;
    Node<Integer> current = head;
    Node<Integer> next = null;
    while(current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    head = prev;
    return head;
}
public static boolean isPallindrome(Node<Integer> head) {
    if(head == null || head.next == null) {
        return true;
    }

    Node<Integer> fast = head;
    Node<Integer> slow = head;

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

    Node<Integer> secondHead = slow.next;
    slow.next = null;
    secondHead = reverseLL(secondHead);

    Node<Integer> p = secondHead;
    Node<Integer> q = head;
    while(p != null) {
        if(p.data != q.data) {
            return false;
        }
        p = p.next;
        q = q.next;
    }
    return true;
}

1 Ответ

2 голосов
/ 04 февраля 2020

Я не собираюсь запускать ваш код, потому что он не завершен. Однако, похоже, что вы нашли последний элемент списка и перевернули его оттуда, не принимая во внимание, что он также переворачивает список, на который вы уже ссылаетесь с помощью head. Поэтому, когда вы начинаете сравнение l oop, у вас есть указатель на первый элемент в обращенном списке и указатель на последний элемент в обращенном списке. Вы определенно не разделяете список на две части.

Ваш код также слишком сложен. Правильный алгоритм: 

find head and tail of list
while (head != tail) {
    if (head.value != tail.value)
        return false;
    head = head.next;
    tail = tail.prev;
}

Вам не нужны две переменные l oop, чтобы найти хвост связанного списка. Правильный алгоритм: 

tail = head
while (tail.next != null) {
    tail = tail.next;
}

Кроме того, вы не можете вообще сравнивать целые числа с оператором равенства. Вы должны либо распаковать их в примитивные целые, либо использовать равные. Попробуйте запустить: 

System.err.println(new Integer(1) == new Integer(1));
System.err.println(new Integer(1).equals(new Integer(1)));
...