思路一：数组+双指针
将链表中的值复制到数组中，然后使用双指针分别从数组的头尾进行遍历，判断两个位置的值是否相等，如果遍历完数组发现是回文数组就返回true，否则返回false
/*** 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> value;ListNode* temp = head;while(temp != nullptr){value.emplace_back(temp->val);temp = temp->next;}int left = 0, right = value.size() - 1;while(left < right){if(value[left] != value[right]){return false;}left++;right--;}return true;}
};- 时间复杂度：O(N)
- 空间复杂度：O(N)
思路二：快慢指针
1.使用快慢指针找到链表前半部分的尾部
- 快慢指针先指向链表的表头，快指针每次移动两个单位的位置，慢指针每次移动一个单位的位置
- 若快指针的后继的后继为空，那么说明慢指针已经找到了前半部分的尾部节点
- 注：当链表中节点数目为奇数时，中间的节点被视为是前半部分的节点，不会参与后半部分链表的反转
解释：
链表节点数目为5（奇数）
1->2->3->2->1
初始时
slow：1
fast：1
第一次指针移动：（slow移动一个单位，fast移动两个单位）
slow：2
fast：3
第二次指针移动：
slow：3
fast：5
由于快指针的后继的后继为空，指针不再进行移动，slow指针的位置就是前半部分链表的尾部
2.对链表后半部分进行反转
- 不断将当前节点的后继修改为当前节点的前驱，当当前节点为空时说明链表已经完全被反转
3.判断是否为回文链表
- 分别使用两个不同的指针同时对前半部分和后半部分进行遍历，如果两个指针遍历到的节点对应的值相同就说明是回文链表
-
/*** 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) {//寻找前半部分链表的尾部节点，也就是slow最终返回的值ListNode* slow = head;ListNode* fast = head;while(fast->next != nullptr && fast->next->next != nullptr){slow = slow->next;fast = fast->next->next;}//将后半部分节点进行反转ListNode* pre = nullptr;//前驱指针ListNode* cur = slow->next;//当前要进行反转的节点while(cur != nullptr){ListNode* nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}//判断是否回文ListNode* first = head;ListNode* second = pre;while(second != nullptr){if(first->val != second->val){return false;}first = first->next;second = second->next;}return true;} }; -
时间复杂度：O(n)
-
空间复杂度：O(1)
