给你一个单链表的头节点?head
?,请你判断该链表是否为回文链表。如果是,返回?true
?;否则,返回?false
?。
示例 1:
输入:head = [1,2,2,1] 输出:true
示例 2:
输入:head = [1,2] 输出:false
提示:
[1, 105]
?内0 <= Node.val <= 9
将链表转为数组,然后双指针判断即可。
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vt; // 栈存放数组
while(head){ // 链表 -> 栈
vt.push_back(head->val);
head = head->next;
}
// 定义双指针来对数组进行回文判断
int left = 0, right = vt.size()-1;
while(left < right){
if(vt[left++] != vt[right--]){
return false;
}
}
return true;
}
};
这里因数组大小不好定义,所以可以使用 栈vector
反转链表,同时遍历,若不同,则返回false。
不知道为何这个方法总是返回false
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
ListNode* next;
while(cur){
next = cur->next; // cur的后面结点
cur->next = prev; // cur的前面结点
prev = cur;
cur = next;
}
return prev;
}
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* reverse = reverseList(head);
while(reverse && head){
if(reverse->val != head->val){
return false;
}
reverse = reverse->next;
head = head->next;
}
return true;
}
};