Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Example 1:
Input: head = [1,2,2,1] Output: true
Example 2:
Input: head = [1,2] Output: false
Constraints:
[1, 105].0 <= Node.val <= 9Follow up: Could you do it in
O(n) time and O(1) space?
/**
* 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) {}
* };
*/
// O(3n)
// class Solution {
// public:
// bool isPalindrome(ListNode* head) {
// vector <int> v;
// auto slow = head, fast = head;
// bool odd = false;
// while (fast){
// fast = fast->next;
// if (fast){
// fast=fast->next;
// slow = slow->next;
// } else odd = true;
// }
// // slow is at middle... rotate the 1st part of LL
// auto curr = head, succ = head, prev = head;
// prev = NULL;
// for (;curr!=slow;){
// succ = curr->next;
// curr->next = prev;
// prev = curr;
// curr = succ;
// }
// // if odd, then leave the index slow was at... else start from there
// if (odd)
// slow = slow->next;
// // prev is at the head of 1st part, slow is at head of second
// while(slow && prev){
// // cout << prev->val << "============" << slow->val << endl;
// if (prev->val!=slow->val)
// return false;
// prev = prev->next;
// slow= slow->next;
// }
// return true;
// }
// };
// O(2n)
class Solution {
public:
bool isPalindrome(ListNode* head) {
auto slow=head, fast=head, prev=head, prevv=head;
prev=nullptr;
while(fast && fast->next){
fast=fast->next->next;
prevv = prev;
prev = slow;
slow=slow->next;
prev->next=prevv;
}
if(fast) // odd palindrome ?
slow=slow->next;
while(slow){
// cout << slow->val << "=?" << prev->val << endl;
if(slow->val!=prev->val)
return false;
slow=slow->next;
prev=prev->next;
}
return true;
}
};/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
// find middle (ie, start of 2nd half)
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// reverse the 2nd half [head2 at slow]
ListNode prev = null, succ = slow;
while (slow != null) {
succ = slow.next;
slow.next = prev;
prev = slow;
slow = succ;
}
// compare
while (prev != null && head != null) {
if (head.val != prev.val)
return false;
head = head.next;
prev = prev.next;
}
return true;
}
}