[Algorithm] Leetcode_ Palindrome Linked List_ C++

#Palindrome Linked List

Problem

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

Example 2:

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

Constraints:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9

Follow up:

Could you do it in O(n) time and O(1) space?

Code

C++

class Solution
{
public:
    bool isPalindrome(ListNode *head)
    {
        if (head->next == NULL)
            return true;
        int size = 1;
        ListNode *forward = head;
        ListNode *back = head;
        while (back->next != NULL)
        {
            size++;
            back = back->next;
        }
        back = head;
        for (int i = 0; i < size / 2; i++)
        {
            back = back->next;
        }
        ListNode *prev = NULL;
        ListNode *next = back->next;
        while (next != NULL)
        {
            back->next = prev;
            prev = back;
            back = next;
            next = next->next;
        }
        back->next = prev;
        while (back != NULL)
        {
            if (forward->val != back->val)
                return false;
            forward = forward->next;
            back = back->next;
        }
        return true;
    }
};