Check if a Linked List is a Palindrome in C++

This C++ program demonstrates how to determine whether a singly linked list is a palindrome. A palindrome linked list reads the same forwards and backwards, much like a palindrome string.

Program Code

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Helper function to reverse a linked list and return new head
ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* current = head;
    ListNode* next = NULL;
    while (current != NULL) {
        next = current->next; // Store next
        current->next = prev; // Reverse current node's pointer
        prev = current; // Move pointers one position ahead.
        current = next;
    }
    return prev;
}

// Function to check if the linked list is a palindrome
bool isPalindrome(ListNode* head) {
    if (head == NULL || head->next == NULL) return true;

    // Find the middle of the linked 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
    slow->next = reverseList(slow->next);
    slow = slow->next;

    // Check palindrome
    ListNode* start = head;
    while (slow != NULL) {
        if (start->val != slow->val) return false;
        start = start->next;
        slow = slow->next;
    }

    return true;
}

// Helper function to print the linked list
void printList(ListNode* node) {
    while (node != NULL) {
        std::cout << node->val << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    // Create a linked list: 1->2->2->1
    ListNode* a = new ListNode(1);
    a->next = new ListNode(2);
    a->next->next = new ListNode(2);
    a->next->next->next = new ListNode(1);

    std::cout << "Original List: ";
    printList(a);

    bool result = isPalindrome(a);
    std::cout << "The list is " << (result ? "a palindrome." : "not a palindrome.") << std::endl;

    return 0;
}

Explanation of the Code

The program starts by defining a struct for the linked list node. The isPalindrome function works by first finding the middle of the list using the fast and slow pointer technique. It then reverses the second half of the list and compares it with the first half. If all corresponding values match, the list is a palindrome.

The reversal and comparison are performed in-place without allocating additional space for another list, making this approach space-efficient. The helper functions included are for reversing the list and printing the list’s contents for verification purposes.

Conclusion

This program efficiently checks if a linked list is a palindrome using a two-pointer technique and by reversing the second half of the list. It demonstrates fundamental concepts of linked list manipulation and is a practical example of space-efficient algorithm design.