package coding4fun;

/**
 * Check if a linked list is a palindrome. Must use O(1) space.
 *
 * <pre>
 * Input : 1->2->3->2->1
 * Output: true
 *
 * Input : 1->2->3->3->2->1
 * Output: true
 *
 * Input : 1->2->3->4->1
 * Output: false
 * </pre>
 */
public class Problem49 {
    private static class Node {
        private final int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "" + value;
        }
    }

    public static boolean isPalindrome(Node node) {
        int size = 0;
        for (Node n = node; n != null; n = n.next) {
            size++;
        }

        return false;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        node.next = new Node(2);
        node.next.next = new Node(3);
        node.next.next.next = new Node(2);
        node.next.next.next.next = new Node(1);
        System.out.println(isPalindrome(node)); // true

//        node.next = new Node(2);
//        node.next.next = new Node(3);
//        node.next.next.next = new Node(3);
//        node.next.next.next.next = new Node(2);
//        node.next.next.next.next.next = new Node(1);
//        System.out.println(isPalindrome(node)); // true
//
//        node = new Node(1);
//        node.next = new Node(2);
//        node.next.next = new Node(3);
//        node.next.next.next = new Node(4);
//        node.next.next.next.next = new Node(1);
//        System.out.println(isPalindrome(node)); // false
    }
}

@@ -63,23 +63,26 @@
 rome
-. Must use O(1)
+ without any extra
  spa
@@ -230,16 +230,64 @@
 : false%0A
+ *%0A * Input : 1-%3E2-%3E3-%3E4-%3E2-%3E1%0A * Output: false%0A
  * %3C/pre
@@ -748,28 +748,816 @@
   %7D%0A
-%0A        return fals
+        int mid = size / 2;%0A        Node right = node;%0A        for (int i = 1; i %3C= ((size %25 2 == 0) ? mid : mid + 1); i++) %7B%0A            right = right.next;%0A        %7D%0A        Ref ref = new Ref();%0A        reverse(node, mid, 1, ref);%0A        Node left = ref.node;%0A        for (Node a = left, b = right; a != null %7C%7C b != null; a = a.next, b = b.next) %7B%0A            if (a.value != b.value) %7B%0A                return false;%0A            %7D%0A        %7D%0A        return true;%0A    %7D%0A%0A    private static class Ref %7B%0A        Node node;%0A    %7D%0A%0A    private static Node reverse(Node node, int mid, int i, Ref ref) %7B%0A        if (i == mid) %7B%0A            ref.node = node;%0A            return node;%0A        %7D%0A        Node n = reverse(node.next, mid, i + 1, ref);%0A        node.next = null;%0A        n.next = node;%0A        return nod
 e;%0A 
@@ -1859,18 +1859,44 @@
 / true%0A%0A
-//
+        node = new Node(1);%0A
         
@@ -1912,34 +1912,32 @@
  = new Node(2);%0A
-//
         node.nex
@@ -1950,34 +1950,32 @@
  = new Node(3);%0A
-//
         node.nex
@@ -1993,34 +1993,32 @@
  = new Node(3);%0A
-//
         node.nex
@@ -2041,34 +2041,32 @@
  = new Node(2);%0A
-//
         node.nex
@@ -2094,34 +2094,32 @@
  = new Node(1);%0A
-//
         System.o
@@ -2162,43 +2162,285 @@
 rue%0A
-//%0A//        node = new Node(1);%0A//
+%0A        node = new Node(1);%0A        node.next = new Node(2);%0A        node.next.next = new Node(3);%0A        node.next.next.next = new Node(4);%0A        node.next.next.next.next = new Node(1);%0A        System.out.println(isPalindrome(node)); // false%0A%0A        node = new Node(1);%0A
     
@@ -2468,18 +2468,16 @@
 ode(2);%0A
-//
         
@@ -2506,18 +2506,16 @@
 ode(3);%0A
-//
         
@@ -2549,18 +2549,64 @@
 ode(4);%0A
-//
+        node.next.next.next.next = new Node(2);%0A
         
@@ -2621,32 +2621,37 @@
 t.next.next.next
+.next
  = new Node(1);%0A
@@ -2650,18 +2650,16 @@
 ode(1);%0A
-//
         

Update problem 49