Check if a LinkedList is palindrome or not.

Problem Overview

In this article, we explore the LeetCode problem known as "Palindrome Linked List." The challenge of this problem is to determine whether a given singly linked list is a palindrome. A list is considered a palindrome if it reads the same forwards and backwards, much like a palindrome word (e.g., "radar").

Understanding the Problem

To solve the "Palindrome Linked List" problem, you need to check if the sequence of nodes in a singly linked list is the same when traversed from head to tail as when traversed from tail to head. The linked list consists of nodes with integer values, and you need to return a boolean result indicating whether it is a palindrome.

Key DSA Concepts and Theory

Linked Lists

A linked list is a linear data structure where elements are not stored at contiguous memory locations. Each element of a linked list is represented as a node that contains two parts: data and a pointer/reference to the next node in the sequence.

Palindrome

A palindrome is a sequence that reads the same backward as forward. In the context of a linked list, this means the sequence of values should be symmetric around the center of the list.

Two-Pointer Technique

This problem can be effectively solved using the two-pointer technique, specifically the slow and fast pointer approach. It's a common method in linked list problems and helps to find the middle of the linked list efficiently.

Solution Approach

To identify whether a linked list is a palindrome, you can follow these steps:

1. Find the Middle of the Linked List:

   • Use the slow and fast pointers where slow advances by one step and fast by two steps. By the time fast reaches the end of the list, slow will be at the middle.

2. Reverse the Second Half of the List:

   • Reverse the linked list starting from the node at the slow pointer position. This is necessary to compare the first half with the second half of the list.

3. Compare Both Halves:

   • Compare the nodes of the first half with the nodes of the reversed second half. If all corresponding nodes contain the same data, the list is a palindrome.

4. Restore the List:

   • (Optional) Reverse the second half again to restore the list to its original form, if required.

5. Return the Result:

   • If all corresponding nodes matched, return true. Otherwise, return false.

Here's the step-by-step code to implement the solution:

C++ Implementation

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        
        // Find the middle of the list
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Reverse the second half of the list
        ListNode* prev = nullptr, *curr = slow->next;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        // Compare both halves
        ListNode* firstHalf = head;
        ListNode* secondHalf = prev;
        while (secondHalf) {
            if (firstHalf->val != secondHalf->val) {
                return false;
            }
            firstHalf = firstHalf->next;
            secondHalf = secondHalf->next;
        }
        
        return true;
    }
};

Java Implementation

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

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

        // Reverse the second half of the list
        ListNode prev = null, curr = slow.next;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Compare both halves
        ListNode firstHalf = head;
        ListNode secondHalf = prev;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
        
        return true;
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list a couple of times (finding the middle, reversing the second half, and during comparison).

• Space Complexity: O(1) for the iterative solution, because we are modifying the pointers in the list and using a constant amount of extra space.

Common Mistakes to Avoid

• Forgetting to check if the list is empty or contains just one element (both cases are trivially palindromes).
• Not handling the point where fast pointer can reach the end with even number of nodes, resulting in an incorrect definition of the second half.
• Failing to restore the list if the problem constraints require it to remain unchanged.

Similar Problems on LeetCode

• Reverse Linked List (206)
• Linked List Cycle (141)
• Reorder List (143)

Additional Resources and References

• GeeksforGeeks on Linked Lists
• Introduction to Algorithm Design Patterns

By understanding these concepts and following the step-by-step approach, you can effectively determine if a singly linked list is a palindrome, optimizing both time and space in the process.