Check if a Singly Linked List is Palindrome

Given a singly linked list, determine if its a palindrome. Return 1 or 0 denoting if its a palindrome or not, respectively.

Notes:
- Expected solution is linear in time and constant in space.

For example,

List 1–>2–>1 is a palindrome.
List 1–>2–>3 is not a palindrome.

Solution:

This method takes O(n) time and O(1) extra space.
1) Get the middle of the linked list.
2) Reverse the second half of the linked list.
3) Check if the first half and second half are identical.
4) Construct the original linked list by reversing the second half again and attaching it back to the first half.

/* Program to check if a linked list is palindrome */
#include <iostream>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
};
 
void reverseList(ListNode **head) {
    ListNode *prev = NULL, *ptr = *head, *temp;
    while (ptr) {
        temp = ptr->next;
        ptr->next = prev;
        prev = ptr;
        ptr = temp;
    }
    *head = prev;
}
 
void printList(ListNode *ptr) {
    while(ptr) {
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << endl;
}
 
int isPalindromicLinkedList(ListNode* head) {
    if (head == NULL) {
        return 1;
    }
    ListNode *p1, *p2; // two pointer to struct List Node
 
    // find mid
    ListNode *mid = NULL;
    p1 = p2 = head;
    while (p2) {
        p2 = p2->next;
        if (p2) p2 = p2->next;
        if (p2) p1 = p1->next;
    }
    mid = p1;
 
    reverseList(&(mid->next)); // reverse list ahead of MID
 
    int ans = 1;
    p1 = head;
    p2 = mid->next;
    while (ans == 1 && p2) {
        if (p1->val != p2->val) ans = 0;
        p1 = p1->next;
        p2 = p2->next;
    }
 
    reverseList(&(mid->next)); // reset second half of list to original state.
 
    return ans;
}
 
ListNode *createListFromArray(int arr[], int n) {
    ListNode *head = new ListNode;
    ListNode *ptr = head;
    for (int i = 0; i < n; i++) {
        ptr->val = arr[i];
        ptr->next = (i == n-1 ? NULL : new ListNode);
        ptr = ptr->next;
    }
    return head;
}
 
 
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 4, 3, 2, 1};
    cout << "Result 1: " << isPalindromicLinkedList(createListFromArray(arr, 9)) << endl;
 
    int arr2[] =  {1, 2, 2, 1};
    cout << "Result 2: " << isPalindromicLinkedList(createListFromArray(arr2, 4)) << endl;
 
    int arr3[] = {1, 2, 3, 4, 5};
    cout << "Result 3: " << isPalindromicLinkedList(createListFromArray(arr3, 5)) << endl;
 
    return 0;
}

One Thought on “Check if a Singly Linked List is Palindrome

  1. How can this be in linear if you dont have middle element in the first place? Or Is putting element into stack and comparing elements while dequeueing more efficient?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation