Hey Guys! Today is Day 99 and we are going to do another linked list problem.
Question : 234. Palindrome Linked List
Given the head
of a singly linked list, return true
if it is a palindrome or false
otherwise.
Example 1:
Understanding the Approach(Intuition):
Before diving into the code, let's understand the intuition behind the approach used in the provided C++ code.
The core idea behind this approach is to find the middle of the linked list using the "tortoise and hare" method.
After finding the middle, the code reverses the second half of the linked list.
Finally, it compares the first half of the original linked list with the reversed second half to check if it's a palindrome.
Algorithm:
Sure, I'll explain how the isPalindrome
function works step by step:
-
Find the Middle of the Linked List:
- Initialize two pointers,
slow
andfast
, both pointing to the head of the linked list. - Use the "tortoise and hare" approach, where
slow
moves one step at a time, andfast
moves two steps at a time. - Continue this process until
fast
reaches the end of the linked list or the node just before the end (if the number of nodes is even). This ensures thatslow
ends up at the middle node. - If the number of nodes is odd, move
slow
one more step to skip the middle node (as it doesn't affect palindrome checking).
- Initialize two pointers,
-
Reverse the Second Half:
- Initialize two pointers,
prev
andnextNode
, both initially set toNULL
. - Using the
prev
andnextNode
pointers, reverse the second half of the linked list starting from the node pointed to byslow
. - After this operation, the first half of the original linked list remains unchanged, while the second half is reversed.
- Initialize two pointers,
-
Compare the Halves:
- Initialize a pointer
fast
and set it to the head of the linked list. - Traverse both halves of the linked list simultaneously, comparing the values of nodes pointed to by
slow
andfast
. - If at any point the values do not match, return
false
, indicating that the linked list is not a palindrome. - Continue the comparison until both pointers reach the end of their respective halves.
- Initialize a pointer
-
Return the Result:
- If the comparison loop completes without finding any mismatches (i.e., all values match), return
true
, indicating that the linked list is a palindrome.
- If the comparison loop completes without finding any mismatches (i.e., all values match), return
Code:
bool isPalindrome(ListNode* head) {
//finding the middle element using tortoise hare
ListNode *slow = head, *fast = head;
while(fast!=NULL && fast->next !=NULL){
slow = slow->next;
fast = fast->next->next;
}
//if the no of nodes are odd then move slow to one point
if(fast != NULL && fast->next == NULL){
slow = slow->next;
}
//Reverse the other half
ListNode *prev = NULL;
ListNode *nextNode = NULL;
while(slow != NULL && slow->next != NULL){
nextNode = slow->next;
slow->next = prev;
prev = slow;
slow = nextNode;
}
if(slow != NULL){
slow->next = prev;
}
//comparing the ans
fast = head;
while(slow && fast){
if(slow->val != fast->val){
return false;
}
slow = slow->next;
fast = fast->next;
}
return true;
}
Complexity Analysis
Let's analyze the time and space complexity of this code.
Time Complexity
- The code iterates through the linked list twice. In the worst case, both loops traverse each node of the list, making the time complexity O(n), where n is the number of nodes in the list.
Space Complexity
- The code uses a constant amount of additional space, regardless of the size of the input linked list.
- Thus, the space complexity is O(1), indicating that it uses a fixed amount of memory.
Top comments (0)