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

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

  4. Arko Datta on June 2, 2017 at 10:21 am said:

    The best logic is:-
    function 1: void travfront()
    Here, traverse the list in forward dirn., and concatenate all nos. you get using this logic
    hugeNumber=hugeNumber*10+numberGotJustNowWhileTraversing.
    function 2: void travback(node s)
    Here run a recursive:-
    if(s.nextNode!=null)
    travback(s.nxt);
    Now after this when if function ends, give this again
    hugeNumber2=hugeNumber2*10+numberGotJustNowWhileTraversing.
    It will form the no. backwards.
    If both hugeNumber and hugeNumber2 are equal, you get your palindrome.
    For string linklist concatenate them and rest logic is same.

  5. Arko Datta on June 2, 2017 at 11:01 am said:

    I am giving a java code.

    import java.util.Scanner;
    class Node
    {
    Scanner sc=new Scanner(System.in);
    Node nxt;
    int n;
    Node()
    {
    nxt=null;
    n=0;
    }
    void input()
    {
    System.out.println(“Enter a number: “);
    n=sc.nextInt();
    }
    void display()
    {
    System.out.println(n);
    }
    }
    //This was the node class.

    import java.util.Scanner;
    class palList
    {
    Scanner x=new Scanner(System.in);
    Node p,s;
    int nf,nb;
    void push()
    {//Enter values to the node
    char ans=’y’;
    while(ans==’y’)
    {
    p=new Node();
    p.input();
    if(s==null)
    {
    s=p;
    s.nxt=null;
    }
    else
    {
    p.nxt=s;
    s=p;
    }
    System.out.println(“Do you want to continue? [Y/N]“);
    ans=x.next().trim().charAt(0);
    }
    }

    void display()
    {//Show the values
    for(p=s;p!=null;p=p.nxt)
    p.display();
    }

    void travFront()
    {
    for(p=s;p!=null;p=p.nxt)
    nf=nf*10+p.n;//concatenating all values of node from top
    }

    void travBack(Node ss)
    {
    if(ss.nxt!=null)
    travBack(ss.nxt);
    nb=nb*10+ss.n;//concatenating all values of node from bottom
    }

    int checkPal()
    {
    travFront();
    travBack(s);
    if(nf==nb)
    return 1;
    return 0;
    }

    void main(String args[])
    {//Main menu
    int ch=999;
    palList obj=new palList();
    while(ch!=0)
    {
    System.out.println(“MENU”);
    System.out.println(“1)Insert”);
    System.out.println(“2)Display”);
    System.out.println(“3)Check Palindrome”);
    System.out.println(“0)Exit”);
    System.out.print(“Choice: “);
    ch=x.nextInt();
    switch(ch)
    {
    case 1:
    obj.push();
    break;
    case 2:
    obj.display();
    break;
    case 3:
    int res=obj.checkPal();
    if(res==1)
    System.out.println(“Palindromic List”);
    else
    System.out.println(“Not a palindromic list”);
    break;
    case 0:
    System.out.println(“Program Terminated.”);
    break;
    default:
    System.out.println(“Wrong choice”);
    }
    }
    }
    }
    /**
    OUTPUT 1:

    MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: 1
    Enter a number:
    1
    Do you want to continue? [Y/N]
    y
    Enter a number:
    2
    Do you want to continue? [Y/N]
    y
    Enter a number:
    3
    Do you want to continue? [Y/N]
    y
    Enter a number:
    2
    Do you want to continue? [Y/N]
    y
    Enter a number:
    1
    Do you want to continue? [Y/N]
    n
    MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: 2
    1
    2
    3
    2
    1
    MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: 3
    Palindromic List
    MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: 0
    Program Terminated.

    OUTPUT 2:
    MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: 1
    Enter a number:
    1
    Do you want to continue? [Y/N]
    y
    Enter a number:
    2
    Do you want to continue? [Y/N]
    y
    Enter a number:
    3
    Do you want to continue? [Y/N]
    y
    Enter a number:
    4
    Do you want to continue? [Y/N]
    y
    Enter a number:
    5
    Do you want to continue? [Y/N]
    n
    MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: 2
    5
    4
    3
    2
    1
    MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: 3
    Not a palindromic list
    MENU
    1)Insert
    2)Display
    3)Check Palindrome
    0)Exit
    Choice: 0
    Program Terminated.

    */
    //I was basically talking about this logic:-
    /**
    void travFront()
    {
    for(p=s;p!=null;p=p.nxt)
    nf=nf*10+p.n;//concatenating all values of node from top
    }

    void travBack(Node ss)
    {
    if(ss.nxt!=null)
    travBack(ss.nxt);
    nb=nb*10+ss.n;//concatenating all values of node from bottom
    }

    int checkPal()
    {
    travFront();
    travBack(s);
    if(nf==nb)
    return 1;
    return 0;
    }
    */
    //Rest periphery is lot bigger.
    //I ran the code on BlueJ.

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