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

&nbsp;
Example 1:

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


Example 2:

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


&nbsp;
Constraints:


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


&nbsp;
Follow up: Could you do it in O(n) time and O(1) space?
class Solution:
    def isPalindrome(self, head: "Optional[ListNode]") -> bool:
        if head.next == None: return True #if only 1 element, it's always a palindrome
        forward = head
        first_half = []
        fast = head

        while (fast != None and fast.next != None):
            first_half.append(forward.val)
            forward = forward.next
            fast = fast.next.next

        # forward should now be through half the list
        if fast != None : forward = forward.next  # if length isn't even, skip the middle number
        
        reverse = len(first_half)-1
        while forward != None:
            if forward.val != first_half[reverse]: return False
            forward = forward.next
            reverse -= 1

        return True
class Solution {
    public boolean isPalindrome(ListNode head) {
        
        ListNode mid = getMiddle(head);
        ListNode headSecond = reverse(mid);
        ListNode reverseHead = headSecond;
        
        while(head != null && headSecond != null){
            if(head.val != headSecond.val){
                break;
            }
            head = head.next;
            headSecond = headSecond.next;
        }
        reverse(reverseHead);
        
        return head==null || headSecond == null;
    }
    
    public ListNode reverse(ListNode head){
        if(head==null) return head;
        ListNode prev = null;
        ListNode present = head;
        ListNode next = head.next;
        while(present != null){
            present.next = prev;
            prev = present;
            present = next;
            if(next!=null)
            next = next.next;
        }
        return prev;
    }
    
    public ListNode getMiddle(ListNode head){
        ListNode temp = head;
        int count = 0;
        while(temp!=null){
            temp = temp.next;
            count++;
        }
        int mid = count/2;
        temp = head;
        for(int i=0; i<mid;i++){
            temp = temp.next;
        }
        return temp;
    }
}
class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* prev=nullptr;
        while(head)
        {
            ListNode* current=head->next;
            head->next=prev;
            prev=head;
            head=current;
        }
        return prev;
    }
    bool isPalindrome(ListNode* head) {
         if(!head || !head->next) return true;
        ListNode* tort=head;
        ListNode* hare=head;
        while(hare->next && hare->next->next)
        {
            tort=tort->next;
            hare=hare->next->next;
        }
        tort->next=reverse(tort->next);
         tort=tort->next;
        ListNode* dummy=head;
        while(tort)
        {
            if(tort->val!=dummy->val)
                return false;
            tort=tort->next;
            dummy=dummy->next;
        }
        return true;
    }
};

Time Complexity: O(n/2)+O(n/2)+O(n/2)
Space Complexity: O(1)
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 * this.val = (val===undefined ? 0 : val)
 * this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let slow = head;
    let fast = head;
    // Moving slow one step at a time while fast, two steps
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // This way, slow will end up right after the middle node
    // Reverse the list from that node
    slow = reverse(slow);
    fast = head;
    // Now check for equality first half and second half of the list
    while (slow) {
        if (slow.val !== fast.val) {
            return false;
        }
        slow = slow.next;
        fast = fast.next;
    }
    return true;
};

// Function to reverse a LinkedList
function reverse(head) {
    let prev = null;
    while (head) {
        let nextNode = head.next;
        head.next = prev;
        prev = head;
        head = nextNode;
    }
    return prev;
}
Palindrome Linked List