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

ListNode *prev = NULL, *ptr = *head, *temp;
while (ptr) {
temp = ptr->next;
ptr->next = prev;
prev = ptr;
ptr = temp;
}
}

void printList(ListNode *ptr) {
while(ptr) {
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << endl;
}

return 1;
}
ListNode *p1, *p2; // two pointer to struct List Node

// find mid
ListNode *mid = NULL;
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;
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) {
for (int i = 0; i < n; i++) {
ptr->val = arr[i];
ptr->next = (i == n-1 ? NULL : new ListNode);
ptr = ptr->next;
}
}

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

### 0 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:

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) {
}

}

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[])
int ch=999;
palList obj=new palList();
while(ch!=0)
{
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:

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
1)Insert
2)Display
3)Check Palindrome
0)Exit
1)Insert
2)Display
3)Check Palindrome
0)Exit
Choice: 2
1
2
3
2
1
1)Insert
2)Display
3)Check Palindrome
0)Exit
Choice: 3
Palindromic List
1)Insert
2)Display
3)Check Palindrome
0)Exit
Choice: 0
Program Terminated.

OUTPUT 2:
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
1)Insert
2)Display
3)Check Palindrome
0)Exit
Choice: 2
5
4
3
2
1
1)Insert
2)Display
3)Check Palindrome
0)Exit
Choice: 3
Not a palindromic list
1)Insert
2)Display
3)Check Palindrome
0)Exit
Choice: 0
Program Terminated.

*/
/**
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.

6. Sathish on January 8, 2018 at 8:31 pm said:

This logic works.

boolean flag = true;

if (palindrome.size()%2 != 0) {

for (int i=0,j=palindrome.size()-1; i!=j; i++, j–) {
if (palindrome.get(i) != palindrome.get(j)) {
flag = false;
System.out.println(“Not a Palaondrome”);
break;
}
}

if (flag)
System.out.println(“It is Palindrome”);