给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
解题思路：快慢指针法
1.首先定义两个指针从头节点开始，一个快指针，一个慢指针（快指针一次走两步，慢指针一次走一步）。
2.当快指针走到NULL时，慢指针刚好走到链表中间。
3.反转中间链表后面的节点。
4.定义两个指针，一个从头结点开始，一个从反转后的链表头节点开始，向后遍历比较是否是回文链表。
* struct ListNode {
* int val;
struct ListNode next;
* };
*/
struct ListNode reverse (struct ListNodehead)
{
struct ListNode*pre=NULL;
struct ListNode*cur=head;
while (cur!=NULL)
{
struct ListNode*next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
bool isPalindrome(struct ListNode* head){
struct ListNode*p=head;
struct ListNode*q=head;
while (p->next!=NULL&&p->next->next!=NULL)
{
p=p->next->next;
q=q->next;
}
struct ListNode*z=head;
struct ListNode*s;
s=reverse(q->next);
while (s!=NULL)
{
if (z->val!=s->val)
{
return false;
}
z=z->next;
s=s->next;
}
return true;
}
Original: https://blog.csdn.net/qq_70799748/article/details/127824550
Author: 吃个辣条
Title: 力扣234.回文链表
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/659936/
转载文章受原作者版权保护。转载请注明原作者出处！