牛客网：OR36 链表的回文结构

牛客网：OR36 链表的回文结构

一、题目

 

函数原型：

bool chkPalindrome(ListNode* A)

二、思路

判断一个单链表是否为回文结构，由于单链表不能倒序遍历，所以需要找到单链表的后半段，并将其逆置，再与前半段链表进行比较。

如何找到单链表的后半段呢？

如果链表结点数为偶数个，只要找到单链表的第二个中间结点即可。

如果链表节点数为奇数个，只要找到单链表中间结点的下一个结点即可。

 本题相关题目：

206. 反转链表 - 力扣（LeetCode）

876. 链表的中间结点 - 力扣（LeetCode）

相关题解：

leetcode：206. 反转链表-CSDN博客

leetcode：876. 链表的中间结点-CSDN博客

 三、代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstddef>
ListNode* reserve(ListNode *pphead)//逆置链表函数
{  if(pphead==NULL||pphead->next==NULL)return pphead;else{ListNode *prev =NULL;ListNode *cur=pphead;ListNode *next=pphead->next;while(cur){cur->next=prev;prev=cur;cur=next;if(next)next=next->next;elsenext=NULL;}return prev;}   
}class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code hereListNode *fast=A;ListNode *slow=A;while(fast)//找链表的第二个中间结点或链表中间结点的下一个结点{slow=slow->next;if(fast->next)fast=fast->next->next;elsefast=NULL;}//逆置链表// ListNode *B=NULL;// ListNode *tailB=NULL;// while(slow)// {//     if(tailB==NULL)//     {//         B=tailB=slow;//     }//     else//     {//         tailB->next=slow;//         tailB=slow;//     }//     slow=slow->next;          // }// tailB->next=NULL;ListNode *B=reserve(slow);//逆置链表ListNode *curA=A;ListNode *curB=B;while(curA&&curB)//比较前半段和后半段链表{if(curA->val==curB->val){curA=curA->next;curB=curB->next;}elsereturn false; }return true;}
};