Palindrome Linked List

1package pkg5leetcode.interview150;2 3/*4 * Palindrome Linked List | LC 2345 * APPROACH: Find middle, reverse second half, compare halves.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC234PalindromeLinkedList {9    /** Same shape as pkg5leetcode/common/ListNode.java (nested for single-file runs). */10 11    static class ListNode {12        int val;13        ListNode next;14        ListNode(int val) { this.val = val; }15    }16 17    static boolean isPalindrome(ListNode head) {18        if (head == null || head.next == null) return true;19        ListNode slow = head, fast = head;20        while (fast.next != null && fast.next.next != null) {21            slow = slow.next;22            fast = fast.next.next;23        }24        ListNode second = reverse(slow.next);25        slow.next = null;26        ListNode a = head, b = second;27        while (b != null) {28            if (a.val != b.val) return false;29            a = a.next;30            b = b.next;31        }32        return true;33    }34 35    static ListNode reverse(ListNode head) {36        ListNode prev = null;37        while (head != null) {38            ListNode next = head.next;39            head.next = prev;40            prev = head;41            head = next;42        }43        return prev;44    }45 46    static ListNode of(int... vals) {47        ListNode dummy = new ListNode(0), cur = dummy;48        for (int v : vals) { cur.next = new ListNode(v); cur = cur.next; }49        return dummy.next;50    }51 52    public static void main(String[] args) {53        check(isPalindrome(of(1, 2, 2, 1)), "case1");54        check(!isPalindrome(of(1, 2)), "case2");55        System.out.println("all tests passed");56    }57 58    static void check(boolean cond, String name) {59        if (!cond) throw new AssertionError("FAILED: " + name);60        System.out.println("  PASS " + name);61    }62}