-
Notifications
You must be signed in to change notification settings - Fork 0
/
234-palindrome-linked-list.cpp
77 lines (72 loc) · 2.09 KB
/
234-palindrome-linked-list.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
* 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;
}
};