确定 LinkedList 是否是 palidrome

Question

class ListNode {
int data;
ListNode next;
ListNode(int data) { this.data = data; }
}
public static Boolean isListPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
} 
ListNode n = head;
ListNode fastPointer = head;
ListNode reverse = reverseList(head);
while(fastPointer.next != null || fastPointer != null) {
if(n.data != reverse.data) {
return false;
}
fastPointer = fastPointer.next.next;
reverse = reverse.next;
n = n.next;
}
return true;
}
public static ListNode reverseList(ListNode input) {
ListNode current = input;
ListNode next = input;
ListNode prev = null;
while(current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}

----在反转列表之前----

//ListNode n ： 1 -> 2 -> 3 -> 4 -> 5

----反转列表后----

//列表节点 n ： 1

列表节点反向 ： 5 -> 4 -> 3 -> 2 -> 1

基本上，我在这里所做的是反转链接，然后将原始列表与反向列表进行比较。但是，当我比较编译器时，编译器返回"NullPointerException"。

所以我将代码复制到IntelliJ中，并尝试打印原始和反向列表。原来原来只有一个元素，另一方面，反向列表包含 5 个元素，因为原始列表也应该包含。

我该如何解决这个问题？

Answer 1

我看到你的代码有几个问题。

首先，当您反转列表时，您需要创建一个新列表。当前的方法将反转原始列表。

public static ListNode reverseList(ListNode head)
{
ListNode prev = null;       
ListNode current = head;
while (current != null)
{
ListNode node = new ListNode(current.data);         
node.next = prev;
prev = node;
current = current.next;
}    
return prev;
}

其次，isListPalindrome方法中的测试需要从

while(fastPointer.next != null || fastPointer != null) 

自

while (fastPointer != null && fastPointer.next != null)

通过这两项更改，您的代码就可以工作了。

测试：

ListNode odd = create(1,2,3,2,1);
System.out.format("%s : %b%n", string(odd), isListPalindrome(odd));
ListNode even = create(1,2,3,3,2,1);
System.out.format("%s : %b%n", string(even), isListPalindrome(even));
ListNode non = create(1,2,3,4,5);
System.out.format("%s : %b%n", string(non), isListPalindrome(non));

输出：

1 2 3 2 1 : true
1 2 3 3 2 1 : true
1 2 3 4 5 : false

实用方法：

static ListNode create(int... data)
{
ListNode head, prev;
head = prev = null;
for(int i=0; i<data.length; i++)
{
ListNode node = new ListNode(data[i]);
if(head == null) head = node;
else prev.next = node;
prev = node;            
}
return head;
}
static String string(ListNode head)
{
StringBuffer b = new StringBuffer();
ListNode node = head;
while(node != null)
{
b.append(node.data);
if(node.next != null) b.append(" ");
node = node.next;
}
return b.toString();
}

Answer 2

另一种方法是使用堆栈。简要：

current = head;
while (current != null)
stack.push(current.data);
current = current.next;
current = head;
rslt = true;
while (rslt == true && current != null)
test = stack.pop();
rslt = current.data == test;
}
// at this point, if rslt is true, then the list is a palindrome

Answer 3

这是一个非常简单的解决方案;

boolean isListPalindrome(ListNode<Integer> l) {

if(l == null || l.next == null)return true;

List<Integer> list = new ArrayList<Integer>();
List<Integer> revlist = new ArrayList<Integer>();

while(l != null){
list.add(l.value);
revlist.add(l.value);
l = l.next;
}

Collections.reverse(revlist);

return list.equals(revlist);
}