-
Notifications
You must be signed in to change notification settings - Fork 0
/
palindrome_linked_list.cpp
74 lines (63 loc) · 1.48 KB
/
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
// 234. Palindrome Linked List
// Author: [email protected]
#include <stdio.h>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// Recursive
class Solution1 {
public:
bool isPalindrome(ListNode* head) { return isPalindrome(&head, head); }
private:
bool isPalindrome(ListNode** head, ListNode* tail) {
if (tail == nullptr) {
return true;
}
bool is_pal = isPalindrome(head, tail->next);
if (!is_pal || (*head)->val != tail->val) {
return false;
}
*head = (*head)->next;
return true;
}
};
// Two pointers, reverse first half of linked list
class Solution2 {
public:
bool isPalindrome(ListNode* head) {
ListNode dummy(0);
ListNode* ptr = &dummy;
ListNode* tmp = nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (slow != nullptr && fast != nullptr) {
if (fast->next == nullptr) {
slow = slow->next;
break;
}
fast = fast->next->next;
tmp = slow->next;
slow->next = ptr->next;
ptr->next = slow;
slow = tmp;
}
ptr = dummy.next;
while (slow != nullptr) {
if (ptr->val != slow->val) {
return false;
}
slow = slow->next;
ptr = ptr->next;
}
return true;
}
};
using Solution = Solution2;
int main(int argc, char* argv[]) {
ListNode* head = nullptr;
bool is_pal = Solution().isPalindrome(head);
printf("Is palindrome? %s\n", (is_pal ? "Yes" : "No"));
return 0;
}