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; }
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?
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));
}
}
Much simpler solution
It is not in c++. In C++ you don’t get size from linked list. C++ is raw language.
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;
}
}
}
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.
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.
This logic works.
SingleLinkedListPalindrome traver = new SingleLinkedListPalindrome();
LinkedList palindrome = new LinkedList();
palindrome.add(“m”);
palindrome.add(“o”);
palindrome.add(“m”);
palindrome.add(“o”);
palindrome.add(“m”);
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”);