Palindrome LinkedList

Given the head of a Singly LinkedList, write a method to check if the LinkedList is a palindrome or not.

Your algorithm should use constant space and the input LinkedList should be in the original form once the algorithm is finished. The algorithm should have O(N) time complexity where ‘N’ is the number of nodes in the LinkedList.

Example 1:

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // find mid
        var slow = head;
        var fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        var halfReversed = reverse(slow);
        var halfReversedPoint = halfReversed;
        while (halfReversed != null) {
            if (halfReversed.val != head.val) {
                break;
            }
            halfReversed = halfReversed.next;
            head = head.next;
        }
        reverse(halfReversedPoint);
        if (halfReversed == null || head == null) {
            return true;
        }
        return false;
    }


    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            var next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}