DAY 99 - 234. Palindrome Linked List
Tags: beginners, cpp, algorithms, codenewbie
Published: 2023-09-10 15:49:08

Hey Guys! Today is Day 99 and we are going to do another linked list problem.

---


## Question : [234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/)

Given the _`head`_ of a singly linked list, return `true` if it is a palindrome or `false` otherwise.

---

### Example 1: 

> ![Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7lifyy1zksdm05cj6c3c.png)
> **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:

```cpp

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.