Sponsored
Sponsored
This approach involves reversing the second half of the linked list and then comparing it with the first half. If they are identical, the linked list is a palindrome. The steps include:
Time Complexity: O(n) since we are traversing the list multiple times but each in linear time.
Space Complexity: O(1) as we are reversing the linked list in place.
1#include <stdbool.h>
2#include <stdio.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* reverseList(struct ListNode* head) {
10 struct ListNode* prev = NULL;
11 struct ListNode* current = head;
12 struct ListNode* next = NULL;
13 while (current != NULL) {
14 next = current->next;
15 current->next = prev;
16 prev = current;
17 current = next;
18 }
19 return prev;
20}
21
22bool isPalindrome(struct ListNode* head) {
23 if (head == NULL || head->next == NULL) return true;
24 struct ListNode* slow = head;
25 struct ListNode* fast = head;
26 while (fast != NULL && fast->next != NULL) {
27 slow = slow->next;
28 fast = fast->next->next;
29 }
30 struct ListNode* reversedSecondHalf = reverseList(slow);
31 struct ListNode* p1 = head;
32 struct ListNode* p2 = reversedSecondHalf;
33 while (p2 != NULL) {
34 if (p1->val != p2->val) return false;
35 p1 = p1->next;
36 p2 = p2->next;
37 }
38 return true;
39}The above solution in C reverses the second half of the linked list starting from the middle. We use a fast and slow pointer to find the middle together with reversing the second half and checking for equality.
In this approach, convert the linked list into an array and utilize a two-pointer technique to determine if it forms a palindrome. The steps are as follows:
Time Complexity: O(n) due to single traversation and subsequent O(n/2) check.
Space Complexity: O(n) because we store all node values in an array.
This JavaScript implementation relies on an array to store linked list values. Crosschecking is done using two pointers, validating if input represents a palindromic state.