Palindrome Linked List - Java Solution

1. Introduction

In this post, we'll explore a solution to the "Palindrome Linked List" problem, which involves checking if a singly linked list represents a palindrome. A palindrome is a sequence that reads the same backward as forward. This problem is a great exercise in understanding linked list manipulation and the concept of palindromes.

Problem

The challenge is to determine whether a given singly linked list is a palindrome. The function should return true if the list is a palindrome and false otherwise.

2. Solution Steps

1. Find the middle of the linked list using a slow and fast pointer approach.

2. Reverse the second half of the linked list.

3. Compare the first half and the reversed second half node by node.

4. If all nodes match, return true; otherwise, return false.

5. Restore the list to its original state (optional).

3. Code Program

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class PalindromeLinkedList {
    public static void main(String[] args) {
        // Example use case
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);

        System.out.println(isPalindrome(head)); // Test the function
    }

    // Function to check if a linked list is a palindrome
    public static boolean isPalindrome(ListNode head) {
        if (head == null) return true;

        // Step 1: Find the middle of the linked list
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // Step 2: Reverse the second half
        ListNode prev = null;
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        // Step 3: Compare the two halves
        ListNode left = head;
        ListNode right = prev;
        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }

        // Optional: Restore the list (not shown here)
        return true;
    }
}

Output:

true

Explanation:

1. isPalindrome: This function checks whether a linked list is a palindrome.

2. It first locates the middle of the list using the slow and fast pointer technique.

3. The second half of the list is then reversed. This manipulation allows for direct comparison of the first half with the reversed second half.

4. The function iterates over the first half and the reversed second half simultaneously, comparing the values of corresponding nodes.

5. If all corresponding nodes match, the list is a palindrome; otherwise, it is not.

6. Optionally, the second half of the list can be restored to its original state, though this step is not included in the example.

7. This method efficiently determines if the list is a palindrome with O(n) time complexity and O(1) space complexity.