Palindrome Linked List - CPP Solution

1. Introduction

This blog post addresses a common problem in linked list manipulation: determining whether a singly linked list is a palindrome. A palindrome is a sequence that reads the same backward as forward. This problem involves understanding linked list traversal and reversal techniques.

Problem

Given the head of a singly linked list, the task is to return true if the list is a palindrome or false otherwise.

2. Solution Steps

1. Find the middle of the linked list.

2. Reverse the second half of the list.

3. Compare the first half and the reversed second half of the list.

4. Return true if they are identical, otherwise false.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to find the middle of the list
ListNode* findMiddle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Function to reverse a list
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *current = head, *next = nullptr;
    while (current) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

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

    ListNode* mid = findMiddle(head);
    ListNode* secondHalf = reverseList(mid);
    ListNode* firstHalf = head;

    while (secondHalf) {
        if (firstHalf->val != secondHalf->val) {
            return false;
        }
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }

    return true;
}

int main() {
    // Creating 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);

    bool result = isPalindrome(head);
    cout << "Is palindrome: " << (result ? "true" : "false") << endl;
    return 0;
}

Output:

Is palindrome: true

Explanation:

The isPalindrome function first finds the middle of the list, then reverses the second half of the list. It then compares the nodes of the first half and the reversed second half. If all corresponding nodes are equal, the list is a palindrome. Otherwise, it's not. This approach efficiently checks for palindrome properties in a singly linked list.