# 5.Palindrome Linked List

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

**Example 1:**![](https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg)

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

**Example 2:**![](https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg)

```
Input: head = [1,2]
Output: false
```

**Optimized solution:-**

This solution uses Time Complexity O(n) and Space Complexity O(1).

* Reverse the part of the linked list.
* Iterate over the 1st part and second part an compare the elements. 

```cpp
class Solution
{
public:
    ListNode *rev(ListNode *head)
    {
        if (!head || !head->next)
        {
            return head;
        }

        ListNode *prev = NULL;
        ListNode *p = head;
        ListNode *q = head;

        while (p)
        {
            q = q->next;
            p->next = prev;
            prev = p;
            p = q;
        }

        return prev;
    }

    bool isPalindrome(ListNode *head)
    {

        ListNode *p = head;
        ListNode *q = head;

        while (p && p->next)
        {
            p = p->next->next;
            q = q->next;
        }

        if (p)
        {
            q = q->next;
        }

        q = rev(q);

        p = head;

        while (q)
        {
            if (q->val != p->val)
            {
                return false;
            }

            q = q->next;
            p = p->next;
        }

        return true;
    }
};
```

**Other Solution:-**

Copying all the elements to an array and checking if the array is palindrome. This method uses an extra space complexity of O(n).