Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* h) {
if(h==NULL)
return h;
ListNode *tail=h;
ListNode *p;
p=h->next;
while(p!=NULL)
{
tail->next=p->next;
p->next=h;
h=p;
p=tail->next;
}
tail->next=0;
return h;
}
bool isPalindrome(ListNode* head) {
if(!head || !head->next)
return true;
ListNode *p;
ListNode *p1=head;
ListNode *p2=head->next->next;
//Finding mid of the list 'p' denoted end of first half
while(p2!=NULL && p2->next!=NULL)
{
p=p1;
p1=p1->next;
p2=p2->next->next;
}
p=p1;
//List was of even length
if(p2==NULL)
{
p1=p1->next;
}
else
{
p1=p1->next->next;
}
//Divide the list into two halves
p->next=NULL;
//reverse the second half
p2=reverseList(p1);
p1=head;
//compare the two halves
while(p1 && p2)
{
if(p1->val != p2->val)
return false;
p1=p1->next;
p2=p2->next;
}
return true;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment