234. Palindrome Linked List

目录

一、题目描述

方法一、使用栈

方法二、将链表全部结点值复制到数组，再用双指针法

方法三、递归法逆序遍历链表

方法四、快慢指针+反转链表

---

一、题目描述

234. Palindrome Linked List

方法一、使用栈

需要遍历两次。时间复杂度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;}
};