Approach 1:
The checkPalindrome function takes a vector of integers (arr) as input and checks whether it's a palindrome or not. It uses two pointers, s starting from the beginning of the array and e starting from the end. It iterates through the array and compares elements at s and e. If any mismatch is found, it returns false (0). Otherwise, it continues moving s towards the end and e towards the beginning until s becomes greater than or equal to e, at which point it returns true (1).
The isPalindrome function takes a pointer to the head of a linked list (head) as input and checks whether the linked list is a palindrome or not. It initializes an empty vector arr to store the elements of the linked list. It then traverses the linked list, pushing the data of each node into the vector arr. Finally, it calls the checkPalindrome function with the vector arr as input and returns its result.
This approach converts the linked list into a vector and then checks if the vector is a palindrome, thus solving the problem.
Now, let's analyze the time and space complexity of the provided code:
Time Complexity:
- The time complexity of the isPalindrome function is O(n), where n is the number of nodes in the linked list. This is because it iterates through the entire linked list once to create the vector arr.
- The time complexity of the checkPalindrome function is also O(n), where n is the size of the input vector arr. This is because it iterates through the vector once to check for palindromicity.
Space Complexity:
- The space complexity of the isPalindrome function is O(n), where n is the number of nodes in the linked list. This is because it creates a vector of size n to store the elements of the linked list.
- The space complexity of the checkPalindrome function is O(1), as it only uses a constant amount of extra space regardless of the input size.
Overall, the time complexity of the provided code is O(n), and the space complexity is O(n), where n is the number of nodes in the linked list.
Code:
bool checkPalindrome(vector<int> arr){
int n = arr.size();
int s = 0;
int e = n-1;
while(s<=e){
if(arr[s]!=arr[e]){
return 0;
}
s++;
e--;
}
return 1;
}
bool isPalindrome(LinkedListNode<int> *head) {
// Write your code here.
if(head==NULL || head->next==NULL){
return true;
}
vector<int> arr;
LinkedListNode<int>* temp = head;
while(temp!=NULL){
arr.push_back(temp->data);
temp = temp->next;
}
return checkPalindrome(arr);
}
Approach 2:
Reversing the second half of the list: First, the mid function finds the middle node of the linked list using the slow and fast pointer technique. Then, it returns the pointer to the middle node.
After finding the middle node, the reverse function is used to reverse the second half of the linked list starting from the middle node. This function iterates through the list, reversing the links between nodes.
Once the second half is reversed, the original list is divided into two halves: head1 and head2. head1 points to the first half of the list, and head2 points to the reversed second half.
Then, a comparison is made between head1 and head2. If all corresponding elements match, the list is a palindrome; otherwise, it's not.
Finally, the function returns true if the linked list is a palindrome and false otherwise.
This approach avoids using extra space to store the elements of the linked list in an array, unlike the previous approach.
Let's analyze the time and space complexity of this approach:
Time Complexity:
- Finding the middle node (mid function) takes O(n/2) time, where n is the number of nodes in the linked list.
- Reversing the second half of the list (reverse function) also takes O(n/2) time.
- The comparison between the first and second halves takes O(n/2) time.
- Overall, the time complexity is O(n).
Space Complexity:
- The space complexity is O(1) because the algorithm only uses a constant amount of extra space for pointers and variables, regardless of the size of the input linked list.
Therefore, this approach efficiently determines whether a linked list is a palindrome without using extra space for storing the elements of the list.
Code:
LinkedListNode<int>* reverse(LinkedListNode<int>* head){
LinkedListNode<int>* curr = head;
LinkedListNode<int>* prev = NULL;
LinkedListNode<int>* next = NULL;
while(curr != NULL){
next = curr -> next;
curr -> next = prev;
prev = curr;
curr = next;
}
return prev;
}
LinkedListNode<int>* mid(LinkedListNode<int>* head){
LinkedListNode<int>* slow = head;
LinkedListNode<int>* fast = head->next;
while(fast!=NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
// bool checkPalindrome(vector<int> arr){
// int n = arr.size();
// int s = 0;
// int e = n-1;
// while(s<=e){
// if(arr[s]!=arr[e]){
// return 0;
// }
// s++;
// e--;
// }
// return 1;
// }
bool isPalindrome(LinkedListNode<int> *head) {
// Write your code here.
if(head==NULL || head->next==NULL){
return true;
}
// vector<int> arr;
// LinkedListNode<int>* temp = head;
// while(temp!=NULL){
// arr.push_back(temp->data);
// temp = temp->next;
// }
// return checkPalindrome(arr);
LinkedListNode<int>* middle = mid(head);
LinkedListNode<int>* temp = middle -> next;
middle -> next = reverse(temp);
LinkedListNode<int>* head1 = head;
LinkedListNode<int>* head2 = middle->next;
while(head2!=NULL){
if(head1->data != head2->data){
return false;
}
head1 = head1 -> next;
head2 = head2 -> next;
}
return true;
}