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;
}

4 Thoughts 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?

  2. Vineet Raj on November 12, 2016 at 2:19 pm said:

    public class CheckLinkedListPalindrome {

    public boolean checkIfSinglyLinkedListPalindrome(LinkedList list) {
    boolean flag = true;
    if(list.size()%2 != 0) {
    for(int i=list.size()/2, j=list.size()/2; i0; i++,j–) {
    if(list.get(i+1) != list.get(j-1)) {
    flag = false;
    break;
    }
    }
    } else {
    flag = false;
    }
    return flag;
    }

    public static void main(String[] args) {
    LinkedList list = new LinkedList();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(2);
    list.add(1);
    CheckLinkedListPalindrome checkLinkedListPalindrome = new CheckLinkedListPalindrome();
    System.out.println(checkLinkedListPalindrome.checkIfSinglyLinkedListPalindrome(list));
    }

    }

  3. Eric Mumford on February 13, 2017 at 8:03 am said:

    Most elegant solution is to traverse a string or linked list from element 0 to element(length/2), returning false as soon as a mismatch occurs. This minimizes process cycles.

    function isPal(s) {
    var halfwayPoint = s.substring(0,Math.round(s.length/2)).length;
    for (var pos=0;pos<=halfwayPoint;pos++) {
    var j = s.charAt(pos);
    var k = s.charAt(s.length-pos-1);
    if (j != k) {
    return false;
    }
    if (pos == Math.round(s.length/2)-1) {
    return true;
    }
    }
    }

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