Check if Linked List is a Palindrome – Java Program

This Java program demonstrates how to check if a linked list is a palindrome. The program includes the implementation of the linked list nodes and the logic to check for palindromicity.

Program Structure

The program is structured into three main components:

1. ListNode Class: Defines the node structure for the linked list.
2. PalindromeCheck Class: Contains the method to check if the linked list is a palindrome.
3. Main Class: Contains the main method to execute the program and test the palindrome functionality.

Java Code

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public class PalindromeCheck {
        /**
         * Checks if a linked list is a palindrome.
         * 
         * @param head The head of the linked list.
         * @return True if the linked list is a palindrome, otherwise false.
         */
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) return true;
            
            // Find the middle of the linked list
            ListNode middle = findMiddle(head);
            // Reverse the second half of the list
            ListNode secondHalf = reverse(middle.next);
            ListNode firstHalf = head;
            
            // Compare the first half and the reversed second half
            while (secondHalf != null) {
                if (firstHalf.val != secondHalf.val) return false;
                firstHalf = firstHalf.next;
                secondHalf = secondHalf.next;
            }
            
            return true;
        }
        
        // Helper method to find the middle node of the list
        private ListNode findMiddle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            
            return slow;
        }
        
        // Helper method to reverse a linked list
        private ListNode reverse(ListNode head) {
            ListNode prev = null;
            ListNode current = head;
            
            while (current != null) {
                ListNode next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            
            return prev;
        }
    }

    public class Main {
        public static void main(String[] args) {
            // Create a linked list to test palindrome check
            ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(2, new ListNode(1)))));
            
            // Check if the list is a palindrome
            PalindromeCheck checker = new PalindromeCheck();
            boolean isPalindrome = checker.isPalindrome(head);
            
            // Print the result
            System.out.println("The linked list is " + (isPalindrome ? "a palindrome." : "not a palindrome."));
        }
    }
    

Explanation

ListNode Class: This class represents a node in the linked list. Each node contains an integer value and a reference to the next node.

PalindromeCheck Class: This class contains the method isPalindrome that checks if the linked list is a palindrome. It uses the two-pointer technique to find the middle of the list, reverses the second half of the list, and then compares it with the first half.

Main Class: This class is used for testing the palindrome check functionality. It creates a sample linked list and uses the PalindromeCheck class to determine if it is a palindrome, then prints the result.