题目描述
Given the head of a singly linked list, return true if it is a palindrome.
Example1:
Input: head = [1,2,2,1] Output: true
Example2:
Input: head = [1,2] Output: false
Constraints:
- The number of nodes in the list is in the range [1, 105].
- 0 <= Node.val <= 9
Follow up:
- Could you do it in O(n) time and O(1) space?
解题思路：
- 常规的，可选用一个数组或者一个容器栈来表示，这样用到的空间复杂度就不是O(1)了
- 可以关注后半段，重点是得到链表的中间节点和翻转链表，正好这两个辅助函数都不是很难写，当翻转完链表的后半段，就可以从头开始遍历是否相等，从头开始遍历。
Solution
/**
* 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 {
private:
ListNode* getMid(ListNode* head){
if(head == nullptr){
return head;
}
ListNode* fast = head, *slow = head;
while(fast && fast -> next){
fast = fast -> next -> next;
slow = slow -> next;
}
return slow;
}
ListNode* reverseList(ListNode* head){
if(head == nullptr){
return head;
}
ListNode* node = head;
ListNode* preNode = nullptr;
while(node){
ListNode* nodeNext = node -> next;
node -> next = preNode;
preNode = node;
node = nodeNext;
}
return preNode;
}
public:
bool isPalindrome(ListNode* head) {
// 0 node or 1 node
if(head == nullptr || head -> next == nullptr){
return head;
}
// 2 nodes
if(head -> next -> next == nullptr){
return head -> val == head -> next -> val;
}
ListNode* midNode = getMid(head);
ListNode* reverseHead = reverseList(midNode);
ListNode* node = head;
ListNode* reverseNode = reverseHead;
while(node && reverseNode){
if(node -> val != reverseNode -> val){
return false;
}
node = node -> next;
reverseNode = reverseNode -> next;
}
return true;
}
};
Solution 0918
/**
* 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* fast = head, *slow = head;
while(fast && fast -> next){
fast = fast -> next -> next;
slow = slow -> next;
}
ListNode* nodeRev = reverseList(slow);
ListNode* node = head;
while(node && nodeRev){
if(node -> val != nodeRev -> val){
return false;
}
node = node -> next;
nodeRev = nodeRev -> next;
}
return true;
}
ListNode* reverseList(ListNode* head){
if(head == nullptr){
return head;
}
ListNode* node = head;
ListNode* dummy = nullptr;
while(node){
ListNode* nodeNext = node -> next;
node -> next = dummy;
dummy = node;
node = nodeNext;
}
return dummy;
}
};
