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

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

0 голосов
/ 24 мая 2019

Я пытаюсь решить этот вопрос по leetcode https://leetcode.com/problems/palindrome-linked-list/, но возникают проблемы со строками и строителями строк. По какой-то причине «12» .equals «21» -> возвращает true.

Я попытался преобразовать строку из компоновщика в строку и просто использовал строку компоновщика. 

class Solution {
public boolean isPalindrome(ListNode head) {
    StringBuilder s = new StringBuilder();
    while (head != null) {
        s.append(head.val);
        head = head.next;
    }
    String a = s.reverse().toString(); 
    String b = s.toString(); 
    return a.equals(b);
}
}

Сбой на тестовом примере "12" и возвращает true.

Ответы [ 2 ]

2 голосов
/ 24 мая 2019

StringBuilder reverse не создает новый экземпляр StringBuilder. Это приводит к обращению базовых символов текущего StringBuilder. Таким образом, 

String a = s.reverse().toString(); 
String b = s.toString();

Второй s.toString() работает на оборотной StringBuilder.

ты должен сделать 

String original = s.toString(); 
String reversed = s.reverse().toString();
return original.equals(reversed);
0 голосов
/ 26 мая 2019

Вот тот, который использует только 2 StringBuilders вместо 3 и не использует встроенный обратный метод.Вместо этого цикл while проходит через связанный список, добавляет текущий узел в original StringBuilder и вставляет текущий узел в начало reversed StringBuilder.Таким образом, встроенный метод вставки помогает изменить порядок значений узлов: 

public boolean isPalindrome(ListNode head) {
     StringBuilder original = new StringBuilder(), reversed = new StringBuilder();
     ListNode curr = head;
     while (curr != null) {
         original.append(curr.val);
         reversed.insert(0, curr.val);
         curr = curr.next;
     }
     return original.toString().equals(reversed.toString()) ? true : false;
}
...