2.7 编写一个函数,检查链表是否为回文。
思路:1)可以利用链表中的元素采用头插法创建一个新的链表,然后比较两个链表的元素是否相等。
2)利用快慢指针,将链表后半部分逆转之后,比较前半部分与后半部分是否相等。
3)利用栈将链表中的元素保存,然后弹出与链表中元素比较。
C++实现代码:
#include<iostream>
#include<new>
using namespace std; struct ListNode
{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL) {}
}; void createList(ListNode *&L)
{
int arr[]= {,,,,,,,,,};
int i;
ListNode *p=NULL;
for(i=; i<; i++)
{
ListNode *tmp=new ListNode(arr[i]);
if(L==NULL)
{
L=tmp;
p=tmp;
}
else
{
p->next=tmp;
p=tmp;
}
}
} bool isPalindrome(ListNode *L)
{
if(L==NULL)
return true;
ListNode *L2=NULL;
ListNode *p=L;
ListNode *q=NULL;
ListNode *tmp=NULL;
while(p)
{
tmp=new ListNode(p->val);
if(L2==NULL)
{
L2=tmp;
}
else
{
tmp->next=L2;
L2=tmp;
}
p=p->next;
}
p=L;
q=L2;
while(p&&q)
{
if(p->val!=q->val)
return false;
p=p->next;
q=q->next;
}
if(p==NULL&&q==NULL)
return true;
else
return false;
} int main()
{
ListNode *head=NULL;
createList(head);
ListNode *p=head;
while(p)
{
cout<<p->val<<" ";
p=p->next;
}
cout<<endl;
cout<<isPalindrome(head)<<endl;
}