Java Program to Check if a Linked List is a Palindrome

Introduction

A palindrome is a sequence of elements that reads the same forwards and backwards. Checking if a linked list is a palindrome involves determining if the elements in the list are symmetrical around its center. This guide will walk you through writing a Java program that checks if a singly linked list is a palindrome.

Problem Statement

Create a Java program that:

Implements a singly linked list.
Checks whether the linked list is a palindrome.
Displays the result.

Example:

Input: Linked list: 1 -> 2 -> 3 -> 2 -> 1
Output: The linked list is a palindrome
Input: Linked list: 1 -> 2 -> 3 -> 4 -> 5
Output: The linked list is not a palindrome

Solution Steps

Create the Linked List and Node Structure: Define a Node class to represent each element in the linked list and a LinkedList class to manage the list.
Add Nodes to the Linked List: Implement methods to add nodes to the linked list.
Check if the Linked List is a Palindrome:

Find the middle of the linked list using the two-pointer technique.
Reverse the second half of the linked list.
Compare the first half and the reversed second half.
Restore the list (optional) and determine if it is a palindrome.

Display the Result: Output whether the linked list is a palindrome or not.

Java Program

// Java Program to Check if a Linked List is Palindrome
// Author: https://www.rameshfadatare.com/

class Node {
    int data;
    Node next;

    // Constructor to initialize the node
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // Method to add a new node at the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            // Step 1: Initialize the head if the list is empty
            head = newNode;
        } else {
            // Step 2: Traverse to the end of the list and add the new node
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Method to check if the linked list is a palindrome
    public boolean isPalindrome() {
        if (head == null || head.next == null) {
            return true;
        }

        // Step 3: Find the middle of the linked list
        Node slow = head;
        Node fast = head;

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

        // Step 4: Reverse the second half of the linked list
        Node secondHalf = reverseList(slow);

        // Step 5: Compare the first half and the reversed second half
        Node firstHalf = head;
        Node secondHalfCopy = secondHalf; // Copy of the second half to restore later

        while (secondHalf != null) {
            if (firstHalf.data != secondHalf.data) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        // (Optional) Step 6: Restore the original list by reversing the second half again
        reverseList(secondHalfCopy);

        return true;
    }

    // Helper method to reverse a linked list
    private Node reverseList(Node head) {
        Node prev = null;
        Node current = head;

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

        return prev;
    }

    // Method to display the linked list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class LinkedListPalindrome {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Adding elements to the linked list
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2);
        list.add(1);

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

        // Checking if the linked list is a palindrome
        if (list.isPalindrome()) {
            System.out.println("The linked list is a palindrome.");
        } else {
            System.out.println("The linked list is not a palindrome.");
        }
    }
}

Explanation

Step 1: Initialize the Node Class

The Node class represents a single node in the linked list. Each node contains data and a reference to the next node in the list.
The constructor initializes the node with data and sets the next pointer to null.

Step 2: Initialize the LinkedList Class

The LinkedList class manages the linked list. The class contains the head node that points to the first node in the list.
The add() method appends a new node to the end of the list. If the list is empty, the head node is set to the new node.

Step 3: Find the Middle of the Linked List

The isPalindrome() method uses two pointers, slow and fast, to find the middle of the linked list:
- The slow pointer moves one step at a time.
- The fast pointer moves two steps at a time.
- When fast reaches the end, slow will be at the middle.

Step 4: Reverse the Second Half of the Linked List

The second half of the linked list (starting from slow) is reversed using the reverseList() method.
This method iterates through the list and reverses the pointers to create a new reversed list.

Step 5: Compare the First Half and the Reversed Second Half

The first half of the linked list is compared with the reversed second half to check if the list is a palindrome.
If all corresponding elements are equal, the list is a palindrome.

Step 6: Restore the Original List (Optional)

The original linked list can be restored by reversing the second half again. This step is optional but can be useful if the list needs to be preserved.

Output Example

Original Linked List:
1 -> 2 -> 3 -> 2 -> 1 -> null
The linked list is a palindrome.

Example with Different Input

If you modify the input list to:

list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

The output will be:

Original Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null
The linked list is not a palindrome.

Conclusion

This Java program demonstrates how to check if a singly linked list is a palindrome by using the two-pointer technique, reversing the second half of the list, and comparing the two halves. The program efficiently determines whether the list is symmetrical, providing a useful operation in various scenarios. This exercise is valuable for understanding how to manipulate linked lists and implement palindrome checking algorithms in Java programming.