DAY 99 - 234. Palindrome Linked List

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:

Input: head = [1,2,2,1]
Output: true

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:

1. Find the Middle of the Linked List:

   • Initialize two pointers, slow and fast, both pointing to the head of the linked list.
   • Use the "tortoise and hare" approach, where slow moves one step at a time, and fast 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 that slow 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).

2. Reverse the Second Half:

   • Initialize two pointers, prev and nextNode, both initially set to NULL.
   • Using the prev and nextNode pointers, reverse the second half of the linked list starting from the node pointed to by slow.
   • After this operation, the first half of the original linked list remains unchanged, while the second half is reversed.

3. 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 and fast.
   • 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.

4. 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.

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.