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.
1#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool isPalindrome(ListNode* head) {
vector<int> values;
ListNode* current = head;
while (current != nullptr) {
values.push_back(current->val);
current = current->next;
}
int left = 0, right = values.size() - 1;
while (left < right) {
if (values[left] != values[right]) return false;
left++;
right--;
}
return true;
}In C++, a vector is used to achieve dynamic sizing similar to an array for storing elements, followed by checking with two indices for palindrome verification.