234. Palindrome Linked List | Palindromic Linked List LeetCode Solution in Java | Code with Kamlesh

Palindrome Linked List and LeetCode Solution in Java

Linked lists are a fundamental data structure in computer science and can be used to solve a wide range of problems. One interesting problem involving linked lists is checking whether a given linked list is a palindrome. In this blog post, we will explore what a palindrome linked list is, why it’s an interesting problem, and provide a Java solution for it using LeetCode as a reference,linked list is a palindrome, using LeetCode’s problem “234.

What is a Palindrome Linked List?

A palindrome is a word, phrase, or sequence that reads the same backward as forward. For example, “racecar” and “level” are palindromes. In the context of a linked list, a palindrome linked list is a list where the elements, when read from the beginning to the end and from the end to the beginning, form the same sequence.

Consider the following linked list:

1 -> 2 -> 3 -> 2 -> 1

If we read this linked list from left to right and right to left, we get the same sequence: 1 -> 2 -> 3 -> 2 -> 1. Therefore, this linked list is a palindrome.

Why is Palindrome Linked List an Interesting Problem?

Checking whether a linked list is a palindrome is an interesting problem for several reasons:

1. Real-World Applications: Palindromes are not just a fun linguistic curiosity; they have practical applications. For example, in some compression algorithms and data storage systems, it’s essential to check for palindromic patterns.
2. Algorithmic Challenge: Determining whether a linked list is a palindrome efficiently can be a good algorithmic exercise. It requires careful traversal and comparison of the elements in the linked list.
3. Interviews and Competitive Programming: This problem is a common interview question for software engineering positions and is frequently encountered in competitive programming challenges.

Now, let’s dive into the solution for this problem using Java and LeetCode as our reference platform.

LeetCode Problem Statement

LeetCode is a popular platform for practicing coding problems and algorithm challenges. The problem we’ll be solving is based on LeetCode’s “234. Palindrome Linked List.” Here’s the problem statement:

Problem Statement (LeetCode 234):

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

Approach to Solve the Problem

To determine whether a linked list is a palindrome, we need to compare its elements from the beginning to the end and from the end to the beginning simultaneously. We can use a two-pointer approach for this:

1. Initialize two pointers, slow and fast, both initially pointing to the head of the linked list.
2. Move the fast pointer twice as fast as the slow pointer. This will allow the slow pointer to reach the middle of the linked list when the fast pointer reaches the end.
3. While moving the fast pointer, reverse the first half of the linked list using the slow pointer as you go. This will make it easy to compare the reversed first half with the second half.
4. After reaching the middle of the linked list, continue moving the fast pointer and compare the elements of the reversed first half with the second half of the linked list. If they all match, the linked list is a palindrome.
5. Restore the original linked list by reversing the first half again before returning the result.

Let’s implement this approach in Java.

Java Solution

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class PalindromeLinkedList {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true; // An empty list or a list with a single element is a palindrome.
        }

        // Step 1: Initialize pointers.
        ListNode slow = head;
        ListNode fast = head;

        // Step 2: Move fast pointer and reverse the first half.
        ListNode prev = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next; // Move fast two steps at a time.

            // Reverse the first half of the linked list.
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        // If the list has an odd number of elements, skip the middle element.
        if (fast != null) {
            slow = slow.next;
        }

        // Step 4: Compare the reversed first half with the second half.
        while (slow != null) {
            if (prev.val != slow.val) {
                return false; // The linked list is not a palindrome.
            }
            prev = prev.next;
            slow = slow.next;
        }

        return true; // The linked list is a palindrome.
    }

    public static void main(String[] args) {
        // Example usage:
        // Create a linked list: 1 -> 2 -> 2 -> 1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);

        PalindromeLinkedList solution = new PalindromeLinkedList();
        boolean result = solution.isPalindrome(head);
        System.out.println("Is the linked list a palindrome? " + result); // Output: true
    }
}

Let’s break down the code:

• We define a ListNode class to represent nodes of the linked list, and each node has a val (the value of the node) and a next reference (pointing to the next node in the list).
• In the isPalindrome method, we first handle the base cases: if the list is empty or contains only one element, it is considered a palindrome.
• We initialize two pointers, slow and fast, and use the fast pointer to reach the middle of the linked list while reversing the first half using the slow pointer.
• After reaching the middle, we compare the elements of the reversed first half with the second half of the linked list. If they all match, the linked list is a palindrome.
• Finally, we return the result, and in the example usage in the main method, we create a sample linked list to test our solution.

Complexity Analysis

The time complexity of our solution is O(n), where n is the number of nodes in the linked list. This is because we traverse the entire linked list once.

The space complexity is O(1) since we only use a constant amount of extra space for our pointers and variables, regardless of the size of the linked list.

Conclusion

In this blog post, we explored the concept of a palindrome linked list and why it’s an interesting problem. We also provided a detailed Java solution to check whether a linked list is a palindrome, using LeetCode’s problem “234. Palindrome Linked List” as a reference. This problem is a great example of how data structures like linked lists can be used to solve real-world problems and improve your algorithmic skills.

If you’re preparing for coding interviews or enjoy solving algorithmic challenges, practicing problems like this one on platforms like LeetCode can be a valuable experience. Palindrome linked lists are just one example of the many interesting problems you may encounter in your coding journey, linked list is a palindrome, using LeetCode’s problem “234.

Thank You!

Read More –

206. Reverse Linked List | Reverse Linked List LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/what-is-reverse-linked-list-leetcode-solution-in-java/

Contains Duplicate LeetCode Solution in Java | Leet code Must Do Questions | Code with Kamlesh – https://kamleshsingad.com/contains-duplicate-leetcode-solution-in-java/

Two Sum II – Input Array Is Sorted | Two Sum II – Input Array Is Sorted LeetCode Solution in Java – https://kamleshsingad.com/two-sum-ii-input-array-is-sorted-leetcode-solution-in-java/