Algorithm Puzzles everyday every week sometimes: Palindrome Linked List
Puzzle
Puzzle from leetcode:
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
bool isPalindrome(ListNode* head) const {
std::vector<int> que;
while(head) {
que.emplace_back(head->val);
head = head->next;
}
const size_t queLen = que.size();
const size_t halfLen = queLen / 2;
for(int i = 0; i < halfLen; ++i) {
if(que[i] != que[queLen - i - 1]){
return false;
}
}
return true;
}
};
|
T.C.: O(2N)
S.C.: O(N)
![]()
