Linked List Panlindrome
/***
check
linked list palindrome
Space
Complexity: O(n) Time: O(n)
***/
#include<iostream>
#include<stack>
using namespace std;
struct node {
char ch;
node *next;
};
bool ispalindrome(node *head) {
stack<char> reversell;
node *ptr = head;
while (ptr != nullptr)
{
reversell.push(ptr->ch);
ptr = ptr->next;
}
ptr = head;
while(ptr != nullptr) {
if (ptr->ch != reversell.top()) return false;
else {
reversell.pop();
ptr = ptr->next;
}
}
return true;
}
void main() {
node n[5];
for(int i = 0; i<4; i++)
n[i].next = &n[i+1];
n[4].next = nullptr;
n[0].ch = 'a';
n[1].ch = 'b';
n[2].ch = 'c';
n[3].ch = 'b';
n[4].ch = 'a';
node *p = n;
if (ispalindrome(p))
{
cout<<"palindrome"<<endl;
}
}
If requirements is implemented in place, it can be solved by reverse the second half linked list. And using two pointer, one from head and the other from half, then compare each other until the latter one reach the end of linked list.
ReplyDeletenode* reverseLinkedlist(node *n) {
ReplyDeletenode *p = nullptr;
while (n != nullptr)
{
node *temp = n->next;
n->next = p;
p = n;
n = temp;
}
return p;
}
bool ispalindrome(node *head) {
int cnt = 0;
node *p = head;
while (p != nullptr)
{
cnt++;
p = p->next;
}
int index = cnt/ 2; //ceiling round
p = head;
//reverse the second half
while (index != 0)
{
index--;
p = p->next;
}
node *temp = p->next;
node *hf = reverseLinkedlist(temp);
p = head;
while (hf != nullptr) {
if (p->ch != hf->ch) return false;
p = p->next;
hf = hf->next;
}
return true;
}