当前位置: 首页> 游戏> 攻略 > 【leetcode】回文链表-25-3

【leetcode】回文链表-25-3

时间:2025/7/18 2:01:24来源:https://blog.csdn.net/qq_43552933/article/details/141251384 浏览次数:0次

在这里插入图片描述
方法:快慢指针+递归+遍历

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:// int ListLength=0;ListNode* reverseList(ListNode* head){if(!head||!head->next){// if(head){//     ListLength+=1;// }return head;}ListNode* T=reverseList(head->next);head->next->next=head;head->next=nullptr;// ListLength+=1;return T;}bool isPalindrome(ListNode* head) {if(!head||!head->next){return true;}ListNode* secondStart=searchHalfStart(head);ListNode* b=reverseList(secondStart->next);ListNode* a=head;int eqIndex=0;// while(b){//     std::cout<<"<<<"<<b->val<<std::endl;//     // a=a->next;//     b=b->next;// }bool res=true;while(res && a && b){// std::cout<<eqIndex<<","<<ListLength<<std::endl;// std::cout<<a->val<<"---"<<b->val<<std::endl;if(a->val == b->val){// eqIndex+=1;res=true;a=a->next;b=b->next;// std::cout<<"222"<<std::endl;}else{res=false;break;}}reverseList(secondStart);// std::cout<<eqIndex<<","<<ListLength<<std::endl;return res;}ListNode* searchHalfStart(ListNode* head){ListNode* fast=head;ListNode* slow=head;while(fast->next!=nullptr && fast->next->next!=nullptr){fast=fast->next->next;slow=slow->next;}return slow;}
};

在这里插入图片描述
方法:递归回退策略

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* frontPoint;bool recurveCheck(ListNode* head){if(!head){return true;}else{bool res=recurveCheck(head->next);if(res && head->val==frontPoint->val){frontPoint=frontPoint->next;return res;}else{return false;}}}bool isPalindrome(ListNode* head) {if(!head||!head->next){return true;}frontPoint = head;bool res = recurveCheck(head);return res;}
};

在这里插入图片描述
方法:容器数组+遍历

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {vector<int> vec;ListNode* temp=head;while(temp!=nullptr){vec.emplace_back(temp->val);temp=temp->next;}bool res=true;int i=0,j=vec.size()-1;while(i<j){if(vec.at(i)==vec.at(j)){i++;j--;}else{res=false;break;}}return res;}
};
关键字:【leetcode】回文链表-25-3

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: