LeetCode #234. Palindrome Linked List

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; } }