LeetCode "Palindrome Linked List"

O(n) time O(n) space solution using stack<int>:

class Solution 
{
public:
    bool isPalindrome(ListNode* head) 
    {
        if (!head || !head->next) return true;

        int cnt = 0;
        ListNode *p = head;
        while (p)
        {
            cnt++;
            p = p->next;
        }

        int pivot = cnt / 2;
        stack<int> stk;
        int i = 0;
        p = head;
        while (p)
        {
            if (i < pivot)
            {
                stk.push(p->val);
            }
            else if ((cnt % 2) ?i > pivot : i>=pivot)
            {
                if (stk.empty() || p->val != stk.top()) return false;
                stk.pop();
            }
            p = p->next;
            i++;
        }

        return true;
    }
};

View Code

O(1) space solution, we can reverse one half of it.

class Solution
{    
    ListNode* reverseList(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return head;

        ListNode *p0 = head;
        ListNode *p1 = head->next;
        ListNode *p2 = p1 ? p1->next : nullptr;

        head->next = nullptr;
        while (p0 && p1)
        {
            p1->next = p0;

            p0 = p1;
            p1 = p2;
            p2 = p2 ? p2->next : nullptr;
        }

        return p0;
    }
public:
    bool isPalindrome(ListNode* head)
    {
        if (!head) return true;

        // Split 
        ListNode *ps = head;
        ListNode *pf = ps->next;
        while (pf && pf->next && pf->next->next)
        {
            ps = ps->next;
            pf = pf->next->next;
        }
        ListNode *h2 = ps->next;
        ps->next = nullptr;

        //    Reverse
        h2 = reverseList(h2);
        while (head && h2)
        {
            if (head->val != h2->val) return false;
            head = head->next;
            h2 = h2->next;
        }
        return true;
    }
};

View Code