Check if a linkedlist is palindrome (Recursively)

Question

I am trying with the below code, but the result is always true;

public boolean isPallindrome(Link link, Link right) {
    if (right == null)
        return true;

    if (!isPallindrome(link, right.getNext())) {
        return false;
    }
    boolean isP1 = right.getData() == link.getData();
    link = link.getNext();
    return isP1;
}

Calling: -

System.out.println(link1.isPallindrome(link1.getFirst(), link1.getFirst()));

I think the culprit is the return from where right is checked against null. It is one which might be returning true always. Can some one suggest how to fix this.

Answer 1

This is what your algorithm will look like

boolean flag=true;
public boolean checkPalindrome(List nodeList,boolean flag)
{
    if(flag==false)
        return false;
    if(nodeList.right==null)
        return flag;
    else{
        Node n;//reference for travelling till last node
        //traverse till last node

        //check first and last node

        if(same){
            //delete both nodes;
        }
        else{
            flag=false;
        }
        return checkPalindrome(nodeList,flag)

    }
}

this is just a pointer you need to take it forward.

If at all you need the original list back again, then you might want to copy list contents in other object and use that object in this method

Hope this helps!

Good Luck!

Answer 2

I can go in your approach. you want link.getNext() should have effect on it previous call. you can do it. Just change the function prototype.

public boolean isPallindrome(Link &link, Link right);

Make sure your initial call didnt get affected.

Answer 3

the problem is in:
link = link.getNext(); Your intention here is to make the change reflect in all recursive backward calls, but what you ended up doing is change the reference only locally within the current stack, post that the Left Link is not reflecting in subsequent calls.

If it were C, C++ you could have had the argument as Link** left, Link *right but with references you need to make the Left Link static outside.

Answer 4

I honestly don't follow the general logic of your approach. I'd like to suggest an entirely different one, with some added assumptions.

Is the list in question doubly-linked? If so then you can traverse it from both ends, working from the outside in on either end of the hypothetical palindrome. If the ends ever don't match, then the list is clearly not a palindrome.

Answer 5

You should be using the Java utility classes (or at least implement the interfaces), and definitely bookmark the api. Looking for a pallindrome is fastest if you have a Doubly Linked List, which Java calls a Deque. Unfortunately, this method destroys the original.

public static boolean <E> isPallindrome(Deque<E> deque) {
    if ( deque.size() <= 1 ) {
        return true;
    }
    E first = deque.removeFirst();
    E last = deque.removeLast();
    if ( deque.size() == 0 ) {
        return first.equals(last);
    }
    return isPallindrome(deque)
}

If you want to get fancier, you can use Iterators, and skip the recursion.

If you only have a Linked List, then you'll want a way to get to the end of the list. One way is to keep track of the size of the list. This ends up being O(n^2), because of all the getting.

public static boolean isPallindrome(List<?> list, int size) {
    if ( size <= 1 ) {
        return true;
    }
    if ( ! list.get(0).equals(list.get(size-1)) ) {
        return false;
    }
    return isPallindrome(list.subList(1,size-1));
}

Answer 6

Problem is in your left pointer movement. You will need to stimulate double pointer(or call it a pass by reference) in Java( which is pass by value always) using some container over left pointer. Lets use array of size one as container and it will work. I am using different names here.

public class LinkedListS<T> {

    protected Node head;
    public boolean isPalindrome()
    {
        Node storeHead = head;
        boolean result = isPalindromeUtil(new Node[]{head},head); //have to stimulate pass by reference
        head = storeHead;
        return result;
    }

    private boolean isPalindromeUtil(Node[] left,Node right)
    {
        if(right==null)
            return  true;

        boolean subResult = isPalindromeUtil(left,right.next);
        if (subResult==false)
            return false;

        boolean dataCompareResultForCurrentPosition = false;
        if(left[0].data == right.data)
            dataCompareResultForCurrentPosition = true;

        left[0]=left[0].next; //critical

        return dataCompareResultForCurrentPosition;
    }
}

Answer 7

    public class PalindromeList {
    static Node left;
    public static void main(String[] args) {
        Node node = new Node(5);
        Node node1 = new Node(4, node);
        Node node2 = new Node(7, node1);
        Node node4 = new Node(6, node2);
        Node node5 = new Node(5, node4);
        left = node5;
        System.out.println(isPalindrome(node));
    }


    static boolean isPalindrome(Node right) {
        if (right == null)
            return true;
        boolean isp = isPalindrome(right.next);
        if (isp == false)
            return false;
        boolean isp1 = (right.value == left.value);
        left = left.next;
        return isp1;
    }
}

Answer 8

Virtually keep shrinking the list. In Below code, first call will hold head as first and null as last. In subsequent calls first will become first.next and last will become last but one node's address field's value in a list.

boolean palindromeCheck(List first, List last)
{
    //For even size of List
    if(first == last)
        return true;
    //For odd size of List.
    if(first.next == last)
        return true;
    List newLast = first.next;
    //Traverse till last element.
    while(newLast.next != last)
        newLast = newLast.next;
    //If value is not same, return false.
    if(first.val != newLast.val)
        return false;
    return palindromCheck( first.next, newLast );
}