package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

import java.util.ArrayList;
import java.util.List;

public class _234 {
    public static class Solution1 {
        /**
         * O(n) time
         * O(1) space
         */
        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }

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

            ListNode secondHalfHead = reverse(slow.next);
            ListNode firstHalfHead = head;
            while (firstHalfHead != null && secondHalfHead != null) {
                if (firstHalfHead.val != secondHalfHead.val) {
                    return false;
                }
                firstHalfHead = firstHalfHead.next;
                secondHalfHead = secondHalfHead.next;
            }
            return true;
        }

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

    public static class Solution2 {
        /**
         * O(n) time
         * O(n) space
         */
        public boolean isPalindrome(ListNode head) {
            int len = 0;
            ListNode fast = head;
            ListNode slow = head;
            List<Integer> firstHalf = new ArrayList<>();
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                firstHalf.add(slow.val);
                slow = slow.next;
                len += 2;
            }
            if (fast != null) {
                len++;
            }
            if (len % 2 != 0) {
                slow = slow.next;
            }
            int i = firstHalf.size() - 1;
            while (slow != null) {
                if (firstHalf.get(i--) != slow.val) {
                    return false;
                }
                slow = slow.next;
            }
            return true;
        }
    }

}

@@ -2306,10 +2306,564 @@
 %0A    %7D%0A%0A
+    public static class Solution3 %7B%0A        /**%0A         * O(n) time%0A         * O(n) space%0A         */%0A        public boolean isPalindrome(ListNode head) %7B%0A            List%3CInteger%3E list = new ArrayList%3C%3E();%0A            while (head != null) %7B%0A                list.add(head.val);%0A                head = head.next;%0A            %7D%0A            for (int i = 0, j = list.size() - 1; i %3C= j; i++, j--) %7B%0A                if (list.get(i) != list.get(j)) %7B%0A                    return false;%0A                %7D%0A            %7D%0A            return true;%0A        %7D%0A    %7D%0A%0A
 %7D%0A

refactor 234