脚本宝典收集整理的这篇文章主要介绍了刷题-力扣-面试题 02.06. 回文链表,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/palindrome-linked-list-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
编写一个函数,检查输入的链表是否是回文的。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) {
return true;
}
ListNode* faster = head->next;
ListNode* later = head;
while (faster->next) {
later = later->next;
faster = faster->next;
if (faster->next) {
faster = faster->next;
}
}
// faster 尾节点
// later 中间节点
reversal(later->next);
while (faster) {
if (head->val != faster->val) {
return false;
}
faster = faster->next;
head = head->next;
}
return true;
}
private:
ListNode* reversal(ListNode* p) {
if (!p || !p->next) {
return p;
}
ListNode* nst = p->next;
ListNode* rnst = nst->next;
p->next = nullptr;
while (rnst) {
nst->next = p;
p = nst;
nst = rnst;
rnst = nst->next;
}
nst->next = p;
return nst;
}
};
以上是脚本宝典为你收集整理的刷题-力扣-面试题 02.06. 回文链表全部内容,希望文章能够帮你解决刷题-力扣-面试题 02.06. 回文链表所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。