struct ListNode* reverseList(struct ListNode* head){
//递归
if(head==NULL||head->next==NULL)return head;
struct ListNode p=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return p;
}
bool isPalindrome(struct ListNode head){
if(head==NULL)return true;
struct ListNode *l2=head;
struct ListNode *l1=reverseList(l2);
while(head!=NULL){
if(head->val!=l1->val)
return false;
head=head->next;
l1=l1->next;
}
return true;
}
#include <stdio.h>
struct ListNode
{
int val;
ListNode * next;
};
struct ListNode* clone(struct ListNode* head)
{
ListNode * newhead = new ListNode;
newhead->val = head->val;
ListNode * newp = newhead;
ListNode * p = head;
while (p->next != NULL)
{
newp->next = new ListNode;
newp = newp->next;
p = p->next;
newp->val = p->val;
}
newp->next = NULL;
return newhead;
}
struct ListNode* reverseList(struct ListNode* head){
//递归
if(head==NULL||head->next==NULL)return head;
struct ListNode * p=reverseList(head->next);
ListNode *t = p;
while (t->next != NULL) t = t->next;
t->next = head;
head->next = NULL;
return p;
}
bool isPalindrome(struct ListNode * head){
if(head==NULL)return true;
struct ListNode *l2=clone(head);
struct ListNode *l1=reverseList(l2);
while(head!=NULL){
if(head->val!=l1->val)
return false;
head=head->next;
l1=l1->next;
}
return true;
}
int main()
{
ListNode* head = new ListNode;
head->val = 0;
ListNode *p = head;
for (int i = 1; i < 3; i++)
{
ListNode * n = new ListNode;
n->val = i;
p->next = n;
p = n;
}
for (int i = 2; i >= 0; i--)
{
ListNode * n = new ListNode;
n->val = i;
p->next = n;
p = n;
}
p->next = NULL;
printf("%d", isPalindrome(head));
return 0;
}