Check for palindrome in singly linked list

Question

Looking for code review, optimizations and best practices.

Node.java

 class Node {
    Node next;
    int data;

    public Node(int value) {
        data = value;
    }
}

Palindrome.java

 public class Palindrome {

        static Node reverse(Node head) {

            Node prev = null;
            Node current = head;
            Node next;
            while (current != null) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            head = prev;
            return head;
        }

        static public boolean isPalindrome(Node head) {

            Node current = head;
            int length = 0;

            // Get the length of the LinkedList
            while (current != null) {
                current = current.next;
                length++;
            }
            // Find position of next to mid element
            int mid = length % 2 == 0 ? length / 2 + 1 : length / 2 + 2;

            int idx = mid;
            current = head;

            // Traverse to next to mid element
            while (idx > 1) {
                current = current.next;
                idx--;
            }
            // Reverse right side of the List and return head of the reversed list
            Node head1 = reverse(current);

            boolean isPalindrome = true;
            idx = length / 2;
            current = head;

            // Check reversed list(second half) matches with first half
            while (idx > 0) {

                if (current.data != head1.data) {
                    isPalindrome = false;
                    break;
                }
                current = current.next;
                head1 = head1.next;
                idx--;
            }

            return isPalindrome;
        }

        public static void main(String[] args) {

            Node head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            head.next.next.next = new Node(2);
            head.next.next.next.next = new Node(1);

            System.out.println(isPalindrome(head));
        }
    }

Answer 1

Your inconsistent and unconventional indentation makes your code harder to read than it should be.

Although Java accepts multiple top-level classes in the same file as long as no more than one is public, it is poor form. Every top-level class, interface, and enum should have its own file, whether public or not. Among other things, this makes it much easier to find all the classes, both for you and for the compiler.

It is a bit questionable that you're willing to destroy the list in order to test whether it's palindromic, but inasmuch as you are willing to do so, you could perform your palindrome test more efficiently. You would use two primary Node references, one that advances one position for every two that the other advances. Using the trailing reference, you would reverse the front portion of the list as you go, so that when the lead reference finds the end of the list, the trailing reference is at the midpoint, with a reference to the reversed first half already in hand. I'm sure you see how to proceed from there.

You could also consider using an auxiliary data structure to build the reverse half-list or an equivalent; in particular, pushing the nodes one by one onto a stack would have a comparable effect. This could be done in a way that does not destroy the original list.

Or on the third hand, if you were willing to change to a doubly-linked list, and especially if you were willing to represent the list itself with a separate data structure that contained a reference to the tail in addition to the reference to the head, then the palindrome test could be performed much more simply. You would just start at both ends and work towards the middle. That doesn't modify the list, either.

Answer 2

@PellMel already covered very nicely the various considerations for the logic of checking if the elements form a palindrome. I will focus on techniques.

Improving Node

If the Node class is only used by Palindrome, then it would make sense to make it a static inner class, to hide from outside. This would be good encapsulation / information hiding.

The data in Node is an int, but your algorithm can easily work with anything. Consider using generics, to increase the usefulness of classes.

The data field is never reassigned, so it could be final. It's good to make fields final when you can, to avoid accidental unintended reassignments.

Improving reverse

This method is quite nicely done, but a few improvements can make it better.

prev is an OK name, but perhaps newHead would convey better its purpose and the logic behind it.

next is only used inside the loop, so it can be declared there, instead of outside. It's recommended to declare variables in the smallest scope where they are needed, to prevent accidental misuses.

At the end of the method, you assign prev to head and return head. head is a parameter of the method, and reassigning to method parameters is not recommended. In any case, this reassignment is pointless, because you could simply return prev.

The above suggestions applied, the method becomes:

    static Node reverse(Node head) {
        Node newHead = null;
        Node current = head;
        while (current != null) {
            Node next = current.next;
            current.next = newHead;
            newHead = current;
            current = next;
        }
        return newHead;
    }

Improving isPalindrome

The logic of finding the length could be extracted to its own helper method. It's good to have many small methods that have a single responsibility. It increases modularity and thereby reusability. It also improves encapsulation, by hiding the variables used by the logic of the implementation. A good method name usually obviates the need for a comment to describe the logic.

Similarly, the logic of traversing until the middle can be extracted too, for the same benefits.

head1 is obviously a poor name. How about reversedSecondHalf ? Actually, a common name for a linked list iterator variable is "runner". I would recommend this writing style:

Node runner1 = head;
Node runner2 = reverse(iterateToSecondHalf(head, length));

for (int i = 0; i < length / 2; i++) {
    // ...
}

But the worst part of this method is the flag variable isPalindrome. You don't need it. When you know the list is not a palindrome, instead of setting a variable to false, and crossing fingers that the rest of the method doesn't screw anything up and returns it correctly, you could just return false immediately. If the end of the loop is reached, evidently the list is a palindrome, so you can return true. No flag variable is needed.

Answer 3

1

static public boolean That's an unconventional order, fix to public static boolean.

2

Your algorithm seems to chop of the very last element for some reason. Also, you could rewrite it a bit:

public static boolean isPalindromeV2(Node head) {
    int length = getListLength(head);

    if (length < 2) {
        // An empty list or a list of one node is trivially a palindrome.
        // This also handles the case where 'head' is 'null'. However, you
        // might want to deal with the 'null' case differently. I leave it
        // to you.
        return true;
    }

    int reversedSubListLength = length / 2;
    Node auxHead = null;

    for (int counter = 0; counter < reversedSubListLength; ++counter) {
        Node current = head;
        head = head.next;
        current.next = auxHead;
        auxHead = current;
    }

    Node finger1 = auxHead;
    Node finger2 = head;

    if (length % 2  == 1) {
        // Once here, the list is of odd length: skip the middle element.
        finger2 = finger2.next;
    }

    boolean isPalindrome = true;

    for (int i = 0; i < reversedSubListLength; ++i) {
        if (finger1.data != finger2.data) {
            isPalindrome = false;
            break;
        }

        finger1 = finger1.next;
        finger2 = finger2.next;
    }

    // Reverse the first half of the list so that the input list is in the 
    // same state as it was when passed to this routine.
    for (int counter = 0; counter < reversedSubListLength; ++counter) {
        Node current = auxHead;
        auxHead = auxHead.next;
        current.next = head;
        head = current;
    }

    return isPalindrome;
}

private static int getListLength(Node head) {
    Node node = head;
    int length = 0;

    while (node != null) {
        node = node.next;
        ++length;
    }

    return length;
}

Hope that helps.