Problem Statement

Given a singly linked list, the task is to determine whether it is a palindrome or not. A palindrome linked list is one where the sequence of elements from the head to the tail and from the tail to the head are the same.

Examples

Example 1:

Input: List = 1->2->3->2->1
Output: True

Explanation: Linked list values “1 2 3 2 1” is a palindrome because its elements read the same from left to right and from right to left, making it symmetrical and mirroring itself.

Example 2:

Input: List = 1->1->2->1
Output: false

Explanation: 1121 is not a palindrome.

Different Approach

1️⃣ Brute Force Approach (Using Stack)

A straightforward approach is to use additional data structure to store data temporarily. We can use a stack for it. While visiting each node push data of that node onto the stack. Once all nodes are stored in stack, traverse again the linked list comparing each node's value with the values popped from the top of the stack.

Algorithm:

1. Create an empty stack. This will be used to store the node temporarily from the linked list as we traverse it.
2. Traverse the linked list using a temporary variable till it reaches null.
   1. At each visit to node, push the value of the current node onto the stack.
3. Traverse the linked list again using the temporarily variable again by pointing it to head, till we get to nullptr.
   1. Pop the top element of the stack.
   2. Compare the popped element with the current node's value.
4. If all values matches till we reach the end, it means that the linked list is palindrome, as the values read the same way both forward and backward hence we return true.

Code:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Node class represents a
// node in a linked list
class Node {
public:
    // Data stored in the node
    int data;   
    
    // Pointer to the next node in the list
    Node* next;      

    // Constructor with both data and
    // next node as parameters
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data as a
    // parameter, sets next to nullptr
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};


bool isPalindrome(Node* head) {
    // Create an empty stack
    // to store values
    stack<int> st;

    // Initialize a temporary pointer
    // to the head of the linked list
    Node* temp = head;

    // Traverse the linked list and
    // push values onto the stack
    while (temp != NULL) {
        
        // Push the data from the
        // current node onto the stack
        st.push(temp->data); 
        
         // Move to the next node
        temp = temp->next;  
    }

    // Reset the temporary pointer back
    // to the head of the linked list
    temp = head;

    // Compare values by popping from the stack
    // and checking against linked list nodes
    while (temp != NULL) {
        if (temp->data != st.top()) {
            
            // If values don't match,
            // it's not a palindrome
            return false; 
        }
        
        // Pop the value from the stack
        st.pop();         
        
        // Move to the next node
        // in the linked list
        temp = temp->next; 
    }

     // If all values match,
     // it's a palindrome
    return true;
}



// Function to print the linked list
void printLinkedList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    // Create a linked list with
    // values 1, 5, 2, 5, and 1 (15251, a palindrome)
    Node* head = new Node(1);
    head->next = new Node(5);
    head->next->next = new Node(2);
    head->next->next->next = new Node(5);
    head->next->next->next->next = new Node(1);

    // Print the original linked list
    cout << "Original Linked List: ";
    printLinkedList(head);

    // Check if the linked list is a palindrome
    if (isPalindrome(head)) {
        cout << "The linked list is a palindrome." << endl;
    } else {
        cout << "The linked list is not a palindrome." << endl;
    }

    return 0;
}

Complexity Analysis:

Time Complexity: O(2 * n)

• This is because we traverse the linked list twice:
• Once to push the values onto the stack,
• and once to pop the values and compare with the linked list.
• Both traversal take O(2*n) ~ O(n) time.

Space Complexity: O(n)

• We use a stack to store the values of the linked list, and in the worst case, the stack will have all n values, i.e., storing the complete linked list.

2️⃣ Optimal Approach

The previous approach use O(n) additional space, which can be avoided by reversing only half of the linked list and comparing the first and second halves. If the match, reverse the portion that was originally reversed, and then return true else return false.

Algorithm:

1. Check if the linked list is empty or has only one node. If that's the case, it is a palindrome by definition, so return true.
2. Initialize two pointers, slow and fast, to find the middle of the linked list using the Tortoise and Hare algorithm. The slow pointer advances by one step at a time, while the fast pointer advances by two steps at a time. Continue this until the fast pointer reaches the end of the list or is the second last on the list. The slow pointer will now be in the middle of the linked list.
3. Reverse the second half of the linked list start from the middle (the slow->next node). This is done by calling the reverse linked list function and returning the head of the new reversed linked list.
4. Create two pointers, first and second, where first points to the head of the linked list, and second points to the new head of the reversed second half.
5. Compare data values of nodes from both halves. If the values do not match, it means the list is not palindrome. In this case, return false. else continue moving both first and second pointers through their respective halves, comparing the data values until one of them reaches the end of the list.
6. After the comparison, reverse the second half back to its original state using the reverse linked list function and join back the linked list to its original state.

Code:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Node class represents a
// node in a linked list
class Node {
public:
    // Data stored in the node
    int data;   
    
    // Pointer to the next node in the list
    Node* next;      

    // Constructor with both data and
    // next node as parameters
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data as a
    // parameter, sets next to nullptr
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};

// Function to reverse a linked list
// using the recursive approach
Node* reverseLinkedList(Node* head) {
    // Check if the list is empty
    // or has only one node
    if (head == NULL || head->next == NULL) {
        
        // No change is needed;
        // return the current head
        return head; 
    }

    // Recursive step: Reverse the remaining 
    // part of the list and get the new head
    Node* newHead = reverseLinkedList(head->next);

    // Store the next node in 'front'
    // to reverse the link
    Node* front = head->next;

    // Update the 'next' pointer of 'front' to
    // point to the current head, effectively
    // reversing the link direction
    front->next = head;

    // Set the 'next' pointer of the
    // current head to 'null' to
    // break the original link
    head->next = NULL;

    // Return the new head obtained
    // from the recursion
    return newHead;
}

bool isPalindrome(Node* head) {
    // Check if the linked list is empty
    // or has only one node
    if (head == NULL || head->next == NULL) {
        
         // It's a palindrome by definition
        return true; 
    }
    
    // Initialize two pointers, slow and fast,
    // to find the middle of the linked list
    Node* slow = head;
    Node* fast = head;
    
    // Traverse the linked list to find the
    // middle using slow and fast pointers
    while (fast->next != NULL && fast->next->next != NULL) {
        
        // Move slow pointer one step at a time
        slow = slow->next;  
        
        // Move fast pointer two steps at a time
        fast = fast->next->next;  
    }
    
    // Reverse the second half of the
    // linked list starting from the middle
    Node* newHead = reverseLinkedList(slow->next);
    
    // Pointer to the first half
    Node* first = head;  
    
     // Pointer to the reversed second half
    Node* second = newHead; 
    while (second != NULL) {
        
        // Compare data values of 
        // nodes from both halves
        
        // If values do not match,
        // the list is not a palindrome
        if (first->data != second->data) {
            
            // Reverse the second half 
            // back to its original state
            reverseLinkedList(newHead);  
            
            // Not a palindrome
            return false;
        }
        
         // Move the first pointer
        first = first->next; 
        
        // Move the second pointer
        second = second->next;  
    }
    
    // Reverse the second half
    // back to its original state
    reverseLinkedList(newHead);  
    
    // The linked list is a palindrome
    return true;  
}



// Function to print the linked list
void printLinkedList(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    // Create a linked list with
    // values 1, 5, 2, 5, and 1 (15251, a palindrome)
    Node* head = new Node(1);
    head->next = new Node(5);
    head->next->next = new Node(2);
    head->next->next->next = new Node(5);
    head->next->next->next->next = new Node(1);

    // Print the original linked list
    cout << "Original Linked List: ";
    printLinkedList(head);

    // Check if the linked list is a palindrome
    if (isPalindrome(head)) {
        cout << "The linked list is a palindrome." << endl;
    } else {
        cout << "The linked list is not a palindrome." << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2 * n)
  • This algorithm traverses the linked list twice, dividing it into halves.
  • During the first traversal, it reverses one-half of the list
  • During the second traversal, it compares the elements of both halves. As each traversal covers n/2 elements.
  • The time complexity is calculated as O(n/2 + n/2 + n/2), which simplifies to O(2 * n), ultimately representing O(n).
• Space Complexity: O(1)
  • This approach used constant amount of additional space regardless of the input linked list.