LeetCode #234. Palindrome Linked List

Time Complexity: O(n)

Space Complexity: O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {
        // trivially palindrome
        if (head == null || head.next == null) return true;

        // Find middle
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // If odd length, skip the middle node
        // because in the odd case the middle node is not relevant for nowing if a list is palindrome
        if (fast != null) slow = slow.next;

        // Reverse second half
        ListNode second = reverse(slow);

        // Compare halves
        ListNode p1 = head;
        ListNode p2 = second;
        boolean ok = true;
        while (p2 != null) {
            if (p1.val != p2.val) { 
                ok = false; 
                break; 
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return ok;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
}