1. Introduction

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward. Checking if a given linked list is a palindrome is an interesting problem and can be solved using various techniques. In this blog post, we will explore a method to determine if a linked list is a palindrome using Java.

2. Program Steps

1. Define a Node class to represent each element in the linked list.

2. Create helper functions: insert (to insert nodes) and printList (to print the linked list).

3. To check if the linked list is a palindrome:

– Find the middle of the linked list.

– Reverse the second half of the linked list.

– Compare the first half with the reversed second half.

– Restore the original linked list by reversing the second half again.

3. Code Program

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class PalindromeCheck {

    Node head;

    // Inserts a new Node at the end of the list
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    // Reverse the linked list
    public Node reverse(Node node) {
        Node prev = null;
        Node current = node;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        node = prev;
        return node;
    }

    // Check if the linked list is palindrome
    public boolean isPalindrome(Node node) {
        if (node == null || node.next == null) return true;

        Node slow = node, fast = node;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        slow = reverse(slow);
        Node secondHalf = slow;
        Node firstHalf = node;

        boolean palindrome = true;
        while (slow != null) {
            if (firstHalf.data != slow.data) {
                palindrome = false;
                break;
            }
            firstHalf = firstHalf.next;
            slow = slow.next;
        }

        secondHalf = reverse(secondHalf);
        return palindrome;
    }

    // Print the linked list
    public void printList() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    public static void main(String[] args) {
        PalindromeCheck list = new PalindromeCheck();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(2);
        list.insert(1);

        System.out.println("Linked List:");
        list.printList();

        System.out.println("\nIs Palindrome: " + list.isPalindrome(list.head));
    }
}

Output:

Linked List:
1 2 3 2 1
Is Palindrome: true

4. Step By Step Explanation

1. We start with a basic Node class to represent each element in the linked list.

2. The PalindromeCheck class has a head pointer to the beginning of the list.

3. The insert method allows us to insert elements at the end of the linked list.

4. The reverse function is used to reverse a linked list.

5. The isPalindrome function first determines the middle of the linked list. The second half is then reversed and compared with the first half to determine if the linked list is a palindrome. After the check, the second half is reversed again to restore the original linked list.

6. In the main method, we create a sample linked list, print it, and then check if it's a palindrome.