package com.freetymekiyan.algorithms.level.easy;

import com.freetymekiyan.algorithms.utils.Utils;
import com.freetymekiyan.algorithms.utils.Utils.ListNode;
import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * Given a singly linked list, determine if it is a palindrome.
 * <p>
 * Follow up:
 * Could you do it in O(n) time and O(1) space?
 * <p>
 * Tags: Linked List, Two Pointers
 * Similar Problems: (E) Palindrome Number, (E) Valid Palindrome, (E) Reverse Linked List
 */
public class PalindromeLinkedList {

    private PalindromeLinkedList p;

    /**
     * Use two pointers, one slow pointer, one fast pointer.
     * Move slow pointer to the middle.
     * Reverse the right half of the list.
     * Then compare.
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next;
        slow = reverseList(slow);
        while (slow != null && head.val == slow.val) {
            head = head.next;
            slow = slow.next;
        }
        return slow == null;
    }

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

    @Before
    public void setUp() {
        p = new PalindromeLinkedList();
    }

    @Test
    public void testExamples() {
        ListNode h = Utils.buildLinkedList(new int[]{1, 2});
        Assert.assertFalse(p.isPalindrome(h));
    }

    @After
    public void tearDown() {
        p = null;
    }


}

@@ -150,16 +150,17 @@
 stNode;%0A
+%0A
 import o
@@ -393,16 +393,50 @@
 %0A * %3Cp%3E%0A
+ * Company Tags: Amazon, Facebook%0A
  * Tags:
@@ -638,16 +638,117 @@
     /**%0A
+     * Two Pointers.%0A     * Find the middle node, reverse the right half list, then check each node.%0A
      * U
@@ -780,16 +780,18 @@
  pointer
+ s
 , one fa
@@ -800,16 +800,18 @@
  pointer
+ f
 .%0A     *
@@ -821,33 +821,109 @@
 ve s
-low pointer to the middle
+ to the head of the right half list.%0A     * If there are odd number of nodes, move s one step further
 .%0A  
@@ -957,24 +957,40 @@
  of the list
+ starting from s
 .%0A     * The
@@ -998,16 +998,144 @@
  compare
+ each node's value while s is not null.%0A     * If diff, return false. Else continue.%0A     * After all nodes checked, return true
 .%0A     *
@@ -1481,16 +1481,82 @@
 != null)
+ %7B // Make sure slow is always the head of right half.%0A           
  slow = 
@@ -1558,32 +1558,42 @@
 ow = slow.next;%0A
+        %7D%0A
         slow = r
@@ -1609,16 +1609,84 @@
 t(slow);
+ // Reverse the right half of the list.%0A        ListNode cur = head;
 %0A       
@@ -1709,22 +1709,37 @@
 null
- && head
+) %7B%0A            if (cur
 .val 
-=
+!
 = sl
@@ -1764,19 +1764,61 @@
     
-head = head
+    return false;%0A            %7D%0A            cur = cur
 .nex
@@ -1879,28 +1879,290 @@
 urn 
-slow == null;%0A    %7D%0A
+true;%0A    %7D%0A%0A    /**%0A     * Iterative.%0A     * Create a new head as null, which will be the tail of the reversed list.%0A     * While head is not null:%0A     * %7C Store the next node.%0A     * %7C Reverse head.%0A     * %7C Update new head.%0A     * %7C Move to next.%0A     * Return new head.%0A     */
 %0A   

update palindrome linked list