🔁 Check if a Linked List is a Palindrome – Using Fast & Slow Pointers in C++

⚙️ Problem Statement

Given a singly linked list, determine whether it forms a palindrome.

Input: 1 → 3 → 3 → 3 → 1
Output: Palindrome

🧭 Approach – 3 Simple Steps

We solve this problem in three elegant steps using the slow and fast pointer technique:

1. Find the Middle Node

We use two pointers:

• slow moves one step at a time

• fast moves two steps at a time

When fast reaches the end, slow will be at the middle.

2. Reverse the Second Half

From the middle to the end, we reverse the list using standard pointer reversal.

3. Compare Both Halves

We now compare:

• The first half (from head)

• The reversed second half

If all corresponding elements match → it's a palindrome!

🔍 Dry Run Example

Input: 1 → 2 → 3 → 2 → 1

Length = 5 (odd)

Step 1: Find middle

• slow stops at node 3

• therefore, second half is: 3 → 2 → 1

Step 2: Reverse from middle (i.e, second half)
Reversed part becomes: 1 → 2 → 3

Step 3: Compare

•       Original: 1 → 2 → 3
        Reverse:  1 → 2 → 3
  

  All match → ✅ Palindrome!

💡 Palindrome Check – Core Logic in C++

Here’s the heart of the solution using the slow and fast pointer approach:

bool isPalindrome(node *head)
{
    if (head == nullptr || head->next == nullptr)
        return true;

    // Step 1: Find middle using slow and fast pointers
    node *slow = head;
    node *fast = head;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Step 2: Reverse second half of the list
    node *prev = nullptr;
    node *current = slow;
    node *nextNode = nullptr;

    while (current)
    {
        nextNode = current->next;
        current->next = prev;
        prev = current;
        current = nextNode;
    }

    // Step 3: Compare both halves
    node *firstHalf = head;
    node *secondHalf = prev;

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

    return true;
}

🔚 Conclusion( with complexity )

Using the fast and slow pointer technique is a powerful way to solve linked list problems efficiently. This approach gives us:

• ✅ O(n) time

• ✅ O(1) space (no extra array or stack)

                         Keep coding, keep optimizing! 🚀