aboutsummaryrefslogtreecommitdiff
path: root/palindrome_linked_list.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /palindrome_linked_list.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'palindrome_linked_list.c')
-rw-r--r--palindrome_linked_list.c54
1 files changed, 54 insertions, 0 deletions
diff --git a/palindrome_linked_list.c b/palindrome_linked_list.c
new file mode 100644
index 0000000..5477736
--- /dev/null
+++ b/palindrome_linked_list.c
@@ -0,0 +1,54 @@
+// 234. Palindrome Linked List
+#include "leetcode.h"
+
+/*
+ * given the head of a signly linked list return true if it is a palindrome or
+ * false otherwise.
+ */
+
+struct ListNode {
+ int val;
+ struct ListNode *next;
+};
+
+struct ListNode *reverse_list(struct ListNode *head) {
+ if (!head || !head->next)
+ return head;
+ struct ListNode *tmp = reverse_list(head->next);
+ head->next->next = head;
+ head->next = NULL;
+ return tmp;
+}
+
+bool isPalindrome(struct ListNode *head) {
+ if (!head)
+ return 1;
+ struct ListNode *iter = head, *reversed_half_list;
+ int cnt = 0;
+ bool flag = 1;
+ while (iter) {
+ cnt++;
+ iter = iter->next;
+ }
+ iter = head;
+ for (int i = 0; i < cnt / 2; i++)
+ iter = iter->next;
+ if (!(cnt % 2))
+ reversed_half_list = reverse_list(iter);
+ else if (iter->next)
+ reversed_half_list = reverse_list(iter->next);
+ iter = head;
+ if (cnt == 1)
+ return 1;
+ if (!reversed_half_list)
+ return 0;
+ while (iter && reversed_half_list) {
+ if (iter->val != reversed_half_list->val) {
+ flag = 0;
+ break;
+ }
+ iter = iter->next;
+ reversed_half_list = reversed_half_list->next;
+ }
+ return flag;
+}