Deciding whether LinkedList is a 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;

}

----Before reversing a list----

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

----After reversing a list----

//ListNode n : 1

//ListNode reverse : 5 -> 4 -> 3 -> 2 -> 1

Basically what I did here was to reverse the link and then compare the original list with the reverse one. However, when I compare the compiler returns "NullPointerException".

So I copied the code into IntelliJ, and tried to print the original and the reverse list. Turns out the original one has only 1 element in it, on the other hand, the reverse list contains 5 elements as the original list should also contain.

How do I solve this problem ??

Answer 1

I see a couple of issues with your code.

Firstly, when you reverse the list you need to create a new list. Your current method reverses the original list.

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;
}

Secondly, the test in your isListPalindrome method needs to be changed from

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

to

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

With these two changes your code works.

Test:

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));

Output:

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

Utility methods:

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();
}