diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /palindrome_linked_list.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'palindrome_linked_list.c')
-rw-r--r-- | palindrome_linked_list.c | 54 |
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; +} |