java - 判断链表是否是回文

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

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

所以我将代码复制到 IntelliJ 中，并尝试打印原始列表和反向列表。结果原来的列表只有 1 个元素，另一方面，反向列表包含 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();
}