目录
一、题目描述
方法一、使用栈
需要遍历两次。时间复杂度O(n)，空间复杂度O(n)。
/**
* 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) {
stack<int> S;
ListNode* cur = head;
while(cur){
S.push(cur->val);
cur = cur->next;
}
cur = head;
while(cur){
if(cur->val != S.top()){
return false;
}
cur = cur->next;
S.pop();
}
return true;
}
};方法二、将链表全部结点值复制到数组，再用双指针法
也是需要遍历两次，时间复杂度O(n)。空间复杂度O(n)。
/**
* 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> nums;
nums.reserve(100000);
ListNode* cur = head;
while(cur){
nums.push_back(cur->val);
cur = cur->next;
}
int left = 0;
int right = nums.size()-1;
while(left<right){
if(nums[left]!=nums[right])
return false;
left++;
right--;
}
return true;
}
};方法三、递归法逆序遍历链表
可以用递归法逆序遍历链表。用全局变量正序遍历链表。这样就实现了同时从两端遍历链表。
时间复杂度O（n）。递归栈的深度是n，所以空间复杂度还是O(n)。
/**
* 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 {
ListNode* forward = nullptr;//从链表头向链表尾正向遍历的指针
public:
bool isPalindrome(ListNode* head) {
forward = head;
//题目已经保证head不为nullptr，至少有一个结点
return recursiveCheck(head);
}
//用递归来逆序遍历链表
bool recursiveCheck(ListNode* cur){
if(cur->next){
if(!recursiveCheck(cur->next))
return false;
}
if(cur->val != forward->val)
return false;
forward = forward->next;
return true;
}
};方法四、快慢指针+反转链表
将链表后半部分反转。然后同时遍历前半部分和后半部分，逐个比较。
第一步，用快慢指针法找到链表后半部分的开头结点。如果结点个数是奇数，则正中间的结点算作后半部分的开头也可以。参考leetcode 876. 链表的中间结点-CSDN博客
第二步，反转后半部分链表。参考leetcode 206. 反转链表-CSDN博客
第三步，同时遍历前半部分和后半部分，判断是否回文。
第四步，恢复原链表。
第五步，返回结果。
时间复杂度O(n)。空间复杂度O(1)。
/**
* 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) {
ListNode* slow = head;
ListNode* fast = head;
while(fast&&fast->next){
fast = fast->next->next;
slow = slow->next;
}
ListNode* middle = slow;
//把链表后半部分反转
ListNode* reveredRight = reverse(middle);
ListNode* right = reveredRight;
ListNode* left = head;
bool res = true;
while(left != middle){
if(left->val != right->val){
res = false;
break;
}
left = left->next;
right = right->next;
}
//恢复原链表
reverse(reveredRight);
return res;
}
ListNode* reverse(ListNode* head){
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* nex = nullptr;
while(cur){
nex = cur->next;
cur->next = pre;
pre = cur;
cur = nex;
}
return pre;
}
};