运用栈来判断是否为回文链表
解题思路:
1. 首先统计链表元素的总个数cnt
,然后可通过元素的总个数求得链表的中点位置x = cnt / 2
;
2. 定义cur = head
,然后移动cur
,将链表前半部分的x
个元素依次入栈,最终cur
指针指向第x
元素的下一个元素;
3. 如果cnt
为奇数,则要跳过当前cur
指向的元素进行下一步判断;
4. 比较当前的cur
指向的元素值是否等于栈顶元素:
- 若相等,则将栈顶元素删除,cur
移动到下一个位置;
- 若不相等,则说明链表不是回文链表;
5. 最后判断链表是否为空:若为空,则为回文链表;反之,则不是。
class Solution {
public:
bool isPalindrome(ListNode* head) {
int cnt = 0;
stack<int> stk;
for (auto cur = head; cur != nullptr; cur = cur->next) cnt++; //统计链表元素总个数
int x = cnt / 2; //确定前半部分的元素个数
auto cur = head;
//前半部分链表元素值入栈操作
while (x--) {
stk.push(cur->val);
cur = cur->next;
}
if (cnt % 2) cur = cur->next;
//判断当前元素和栈顶元素是否相同
while (cur) {
if (cur->val != stk.top()) return false; // 若不同,则不是回文链表
else stk.pop(), cur = cur->next; // 若相同,栈顶元素出栈,然后接着比较下一个
}
if (stk.empty()) return true; // 最后若栈为空,则说明为回文元素
return false;
}
};