判断链表是否为回文

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;

}

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

//列表节点 n : 1 -> 2 -> 3 -> 4 -> 5

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

//列表节点 n : 1

//ListNode 反转 : 5 -> 4 -> 3 -> 2 -> 1

基本上我在这里所做的是反转 link 然后将原始列表与反向列表进行比较。但是，当我比较编译器时 returns "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);

}

判断链表是否为回文

Deciding whether LinkedList is a palidrome

java

algorithm

linked-list

list

palindrome