How to Check if a Linked List is a Palindrome: A Comprehensive Guide

In this blog post, we will explore the problem of determining whether a linked list is a palindrome. This is a common question asked in technical interviews, and understanding how to solve it can significantly enhance your coding skills.

Understanding the Problem

A palindrome is a sequence that reads the same backward as forward. For example, the linked list represented as 1 -> 2 -> 1 -> NULL is a palindrome because it reads the same from both directions. Conversely, a linked list like 1 -> 2 -> 3 -> 4 -> NULL is not a palindrome.

Example of Palindrome vs Non-Palindrome

• Palindrome: 1 -> 2 -> 1
• Non-Palindrome: 1 -> 2 -> 3 -> 4

Approach to Solve the Problem

We will discuss two approaches to solve the palindrome check for a linked list:

1. Using an array to store the linked list elements.
2. An optimized approach that uses O(1) space.

Approach 1: Using an Array

In this approach, we will copy the linked list elements into an array and then check if the array is a palindrome. Here are the steps:

1. Create an Array: Traverse the linked list and copy its elements into an array.
2. Check for Palindrome: Use two pointers to compare elements from the start and end of the array.

Time Complexity

• Time Complexity (T.C): O(n) for copying the linked list to an array and O(n/2) for checking the palindrome, resulting in O(n).
• Space Complexity (S.C): O(n) due to the additional array.

Code Implementation

vector<int> arr;
Node* temp = head;
while (temp != NULL) {
    arr.push_back(temp->data);
    temp = temp->next;
}
return checkPalindrome(arr);

bool checkPalindrome(vector<int> arr) {
    int n = arr.size();
    int s = 0, e = n - 1;
    while (s <= e) {
        if (arr[s] != arr[e]) {
            return false;
        }
        s++;
        e--;
    }
    return true;
}

Approach 2: Optimized Approach with O(1) Space

To achieve O(1) space complexity, we can use the following steps:

1. Find the Middle of the Linked List: Use the slow and fast pointer technique to find the middle node.
2. Reverse the Second Half: Reverse the linked list starting from the middle node.
3. Compare Both Halves: Compare the first half and the reversed second half.
4. Restore the Original List (Optional): Reverse the second half back to its original order.

Time Complexity

• Time Complexity (T.C): O(n) for finding the middle, reversing the second half, and comparing both halves, resulting in O(n).
• Space Complexity (S.C): O(1) since we are not using any additional data structures.

Code Implementation

Node* getMid(Node* head) {
    Node* slow = head;
    Node* fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

Node* reverse(Node* head) {
    Node* curr = head;
    Node* prev = NULL;
    while (curr != NULL) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

bool isPalindrome(Node* head) {
    if (head == NULL || head->next == NULL) return true;
    Node* middle = getMid(head);
    Node* secondHalf = reverse(middle->next);
    Node* head1 = head;
    Node* head2 = secondHalf;
    while (head2 != NULL) {
        if (head1->data != head2->data) return false;
        head1 = head1->next;
        head2 = head2->next;
    }
    middle->next = reverse(secondHalf); // Restore the original list
    return true;
}

Conclusion

In this blog post, we discussed how to check if a linked list is a palindrome using two different approaches. The first approach, while straightforward, uses additional space, whereas the second approach is optimized for space efficiency. Understanding both methods equips you with the tools to tackle similar problems in coding interviews and real-world applications.

Feel free to experiment with the code and test it with various linked lists to solidify your understanding. Happy coding!