5.Palindrome Linked List

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

Example 1:

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

Example 2:

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.

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