How to check if linked list is palindrome in java

In this post, we will see how to check if linked list is palindrome or not.

Java Linked List Interview Programs:

• How to reverse a linked list in java
• How to reverse a linked list in pairs in java
• How to find middle element of linked list in java
• How to detect a loop in linked list in java
• Find start node of loop in linkedlist
• How to find nth element from end of linked list
• How to check if linked list is palindrome in java
• Add two numbers represented by linked list in java

Algorithm:

• Find middle element of linked list using slow and fast pointer method .
• Reverse second part of linked list
• Compare first and second part of linked list if it matches then linked list is palindrome.

package org.arpit.java2blog;

public class LinkedListPalindromeCheck{

    private Node head;

    private static class Node {
        private int value;
        private Node next;

        Node(int value) {
            this.value = value;

        }
    }

    public void addToTheLast(Node node) {

        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;

            temp.next = node;
        }
    }

    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }

    // This function will find middle element in linkedlist
    public static Node findMiddleNode(Node head)
    {
        // step 1
        Node slowPointer, fastPointer; 
        slowPointer = fastPointer = head; 

        while(fastPointer !=null) { 
            fastPointer = fastPointer.next; 
            if(fastPointer != null && fastPointer.next != null) { 
                slowPointer = slowPointer.next; 
                fastPointer = fastPointer.next; 
            } 
        } 

        return slowPointer; 
    }

    // Function to check if linked list is palindrome or not
    public static boolean checkPalindrome (Node head)
    {
        // Find middle node using slow and fast pointer
        Node middleNode=findMiddleNode(head);
        // we got head of second part
        Node secondHead=middleNode.next;
        // It is end of first part of linked list
        middleNode.next=null;
        // get reversed linked list for second part
        Node reverseSecondHead=reverseLinkedList(secondHead);

        while(head!=null && reverseSecondHead!=null)
        {
            if(head.value==reverseSecondHead.value)
            {
                head=head.next;
                reverseSecondHead=reverseSecondHead.next;
                continue;
            }
            else
            {
                return false;
            }
        }

        return true;

    }

    public static Node reverseLinkedList(Node currentNode) 
    { 
        // For first node, previousNode will be null 
        Node previousNode=null; 
        Node nextNode; 
        while(currentNode!=null) 
        { 
            nextNode=currentNode.next; 
            // reversing the link 
            currentNode.next=previousNode; 
            // moving currentNode and previousNode by 1 node 
            previousNode=currentNode; 
            currentNode=nextNode; 
        } 
        return previousNode; 
    } 

    public static void main(String[] args) {
        LinkedListPalindromeCheck list = new LinkedListPalindromeCheck();
        // Creating a linked list
        Node head=new Node(1);
        list.addToTheLast(head);
        list.addToTheLast(new Node(2));
        list.addToTheLast(new Node(1));
        list.addToTheLast(new Node(2));
        list.addToTheLast(new Node(1));

        list.printList();

        System.out.println("Linked list palidrome: "+checkPalindrome(head));
    }
}

When you run above program, you will get following output:

1 2 1 2 1 
Linked list palidrome: true