题目----力扣--回文链表
题目
给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true示例 2：
输入：head = [1,2]
输出：false提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
使用链表实现的话，已知回文链表中的元素个数必定是偶数个 那么就可以先判断： 1.如果是奇数个元素那么就必定不是回文链表； 2.如果是偶数个元素再进行判断
因为是单链表 所以只能从头到尾进行遍历
回文链表具有以下特点： 第一个元素和第n个元素相同 第二个元素和第n-1个元素相同 ... 那么我们发现实际上在n/2之前的元素与在n/2之后的元素只不过是将顺序翻了过来 这个时候我们就想到栈的特点：后进先出， 那么也就可以实现将顺序翻过来 这个时候栈内所存的实际上就是与原链表相反的元素顺序 那么可以设置两个指针，一个指向头一个元素 一个指向最后一个元素 一个往后 一个往前 进行对比 元素相同则头指针前进，尾指针不回退； 元素不同则头指针不前进，尾指针回退 进行循环比较，每比较 如果比较到最后尾指针和头指针没有重合的话，那么就说明不是回文链表 反之则是。
代码题解
//先创建回文检索函数
struct ListNode* frontPoiner;
bool recursivelyCheck(struct ListNode* currentNode) {
if (currentNode != NULL) {
if (!recursivelyCheck(currentNode->next)) {
return false;
}
if (currentNode->val != frontPoiner->val) {
return false;
}
frontPoiner = frontPoiner->next;
}
return true;
}
//主要函数
bool isPalindrome(struct ListNode* head) {
frontPoiner = head;
return recursivelyCheck(head);
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-06-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录