题解 | #判断一个链表是否为回文结构#
判断一个链表是否为回文结构
https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类 the head
* @return bool布尔型
*/
bool isPail(ListNode* head) {
if(head==nullptr||head->next==nullptr) return true;
//反转链表
ListNode* pre=nullptr;
ListNode* current=head;
ListNode* nxt;
ListNode* res=new ListNode(-1);//哨兵节点
ListNode* t=res;
//反转后,之前链表不存在,要构建一个新链表保存之前的链表
while(current!=nullptr){
t->next=new ListNode(current->val);
t=t->next;
nxt=current->next;
current->next=pre;
pre=current;
current=nxt;
}
//反转结束后pre为头节点
res=res->next;
while(res!=nullptr && pre!=nullptr){
if(res->val!=pre->val) return false;
else{
res=res->next;
pre=pre->next;
}
}
return true;
}
};
网易游戏公司福利 297人发布