Home » Algorithm » Datastructure » Interviews » Linked List » Check linked list is palindrome or not in java

Check linked list is palindrome or not in java

in , , , - on 17:45:00 - No comments

Check linked list is palindrome or not in Java.

A palindromic number is a number that is the same when written forwards or backwards.

Lets see sample input and output for better understanding:

Algorithm 

We will see Recursive and Iterative approach to check if linked list is palindrome or not in java.

Iterative Approach using Stack:
Step 1: Iterate the linked list and put the elements in the stack.
Step 2: Iterate the linked list again and compare each element with the element on the stack.
Step 3: If the element matches then linked list is palindrome else not.

Iterative Approach using Stack Optimized way:
In the first approach, we put all the elements on the Stack, but we do not really require that.
If we put only half the list on Stack that should be good enough to test whether it is palindrome or not.

Step 1: Find the middle node of the linked list and put the half list on to Stack.
Step 2: From the middle node, continue till the end and compare it will the data on the Stack.
Step 3: If the element matches then linked list is palindrome else not.

Note: Only problem we would be having is to find the middle node in case of odd and even list.
We would find the middle node using tortoise and hare pointer, jumping hare pointer twice and tortoise one node at a time.
If fastPointer points to last element of the linked list, it means list is of odd length else of even length.
Example of odd length: 1 2 3 2 1 -> while skipping two elements, fastPointer will stop at last node.
fastPointer movement will be -> (1 then 3 and 1)

Example of even length: 1 2 2 1  -> while skipping two elements, fastPointer will stop at null node.
fastPointer movement will be -> (1 then 2 and null)


Recursive Approach:
In the Recursive approach, Iterate the linked list till the end and when the call stack returns, compare each element from the end with the start node in such a way comparing,
nth node with first node,
n-1 node with second node.,
n-2 node with third node and so on.


Java Program to Check linked list is Palindrome or not.
package com.javabypatel.linkedlist;

import java.util.Stack;

/*
    Input: 1 -> 2 -> 3 -> 2 -> 1
    Output: Palindrome

    Input: 1 -> 2 -> 2 -> 1
    Output: Palindrome

    Input: 1 -> 1
    Output: Palindrome

    Input: 1
    Output: Palindrome

    Input: 1 -> 2 -> 3 -> 1
    Output: Not Palindrome

 */
public class PalindromeCheck {
    LinkedListNode startNode;
    static LinkedListNode temp;

    public static void main(String[] args) {
        PalindromeCheck palindromeCheck = new PalindromeCheck();
        palindromeCheck.addNode(new LinkedListNode(10));
        palindromeCheck.addNode(new LinkedListNode(20));
        palindromeCheck.addNode(new LinkedListNode(10));
        palindromeCheck.addNode(new LinkedListNode(20));
        palindromeCheck.addNode(new LinkedListNode(10));

        //Print List
        System.out.println("Original List is: ");
        palindromeCheck.printLinkList(palindromeCheck.startNode);
        System.out.println();

        temp = palindromeCheck.startNode;
        boolean result = palindromeCheck.isPalindromeWithStaticPointer(palindromeCheck.startNode);
        System.out.println("Result using static way :" + result);

        Result res = palindromeCheck.isPalindromeWithExplicitResultType(palindromeCheck.startNode,
            palindromeCheck.startNode);
        System.out.println("Result using explicit type way :" + res.result);

        result = palindromeCheck.isPalindromeUsingStack(palindromeCheck.startNode);
        System.out.println("Result using Stack :" + result);

        result = palindromeCheck.isPalindromeUsingStackOptimized(palindromeCheck.startNode);
        System.out.println("Result using Stack optimized way:" + result);
    }

    //Optimized stack way, No need to put all the elements in the stack, only n/2 elements we can put in stack
    //and compare each element from that point with the head of the stack.
    private boolean isPalindromeUsingStackOptimized(LinkedListNode startNode) {
        Stack<Integer> stack = new Stack<>();

        //Find middle elememt
        LinkedListNode fastPointer = startNode;
        LinkedListNode slowPointer = startNode;
        while(fastPointer != null && fastPointer.getNext() != null) {
            stack.add(slowPointer.getData());
            slowPointer = slowPointer.getNext();
            fastPointer = fastPointer.getNext().getNext();
        }

        //If fastPointer points to last element of the linked list, it means list is of odd length else of even length.
        //Example of odd length: 1 2 3 2 1 -> while skipping two elements, fastPointer will stop at last node.
        // fastPointer movement will be -> (1 then 3 and 1)

        //Example of even length: 1 2 2 1  -> while skipping two elements, fastPointer will stop at null node.
        // fastPointer movement will be -> (1 then 2 and null)
        if (fastPointer != null) {
            //odd length, so remove the middle element from the stack
            slowPointer = slowPointer.getNext();
        }

        //slowPointer is at middle node, continue it till end and compare each element with element in stack
        while(slowPointer != null) {
            if (stack.pop() != slowPointer.getData()) {
                return false;
            }
            slowPointer = slowPointer.getNext();
        }
        return true;
    }


    private boolean isPalindromeUsingStack(LinkedListNode startNode) {
        Stack<Integer> stack = new Stack<>();

        LinkedListNode temp = startNode;
        while(temp != null) {
            stack.add(temp.getData());
            temp = temp.getNext();
        }

        while(startNode != null) {
            if (stack.pop() != startNode.getData()) {
                return false;
            }
            startNode = startNode.getNext();
        }
        return true;
    }

    // When we reach the end of recursive stack, we will start comparing,
    // the nth node with first node, the n-1 node with second node and so on.
    // Note: nodes from back that is n, n-1, n-2 .. nodes we can get it easily when the call stack is returned
    // but how to get first, second, third ... nodes.
    // we will be using Result class whose next variable points to startNode till the end of the list and
    // once the call stack recurse back, it proceeds with going further one node at a time and
    // state of that pointer is preserved in Result object which is returned back to the caller method.
    private Result isPalindromeWithExplicitResultType(LinkedListNode node, LinkedListNode startNode) {
        if (node == null) {
            return new Result(true, startNode);
        }

        Result res = isPalindromeWithExplicitResultType(node.getNext(), startNode);
        if(!res.result) {
            return res;
        }

        if (node.getData() != res.next.getData()) {
            return new Result(false);
        }

        res.next = res.next.getNext();
        return res;
    }

    private boolean isPalindromeWithStaticPointer(LinkedListNode node) {
        if (node == null) {
            return true;
        }

        boolean res = isPalindromeWithStaticPointer(node.getNext());
        if(!res) {
            return res;
        }

        if (temp.getData() != node.getData()) {
            return false;
        }

        temp = temp.getNext();
        return true;
    }

    private void printLinkList(LinkedListNode startNode) {
        LinkedListNode tempNode = startNode;
        while(tempNode!=null){
            System.out.print(tempNode.getData() + " ");
            tempNode = tempNode.getNext();
        }
    }

    private void addNode(LinkedListNode node) {
        if (startNode != null) {
            LinkedListNode tempNode = startNode;
            while (tempNode.getNext() != null) {
                tempNode = tempNode.getNext();
            }
            tempNode.setNext(node);
        } else {
            this.startNode = node;
        }
    }
}

class Result {
    boolean result;
    LinkedListNode next;

    Result (boolean result, LinkedListNode next) {
        this.result = result;
        this.next = next;
    }

    Result (boolean result) {
        this(result, null);
    }
}

Output:
Original List is:
10 20 10 20 10
Result using static way :true
Result using explicit type way :true
Result using Stack :true
Result using Stack optimized way:true
Categories: , , ,

Post a Comment