package com.ctci.linkedlists;

import java.util.Stack;

import static com.ctci.linkedlists.Node.printList;

/**
 * @author rampatra
 * @since 2019-02-02
 */
public class Palindrome {

    /**
     * Checks whether a Linked List is palindrome by using a stack.
     * 
     * @param head starting node of the linked list.
     * @return {@code true} if linked list palindrome, {@code false} otherwise.
     */
    private static boolean isPalindrome(Node head) {
        Node curr = head;
        Stack<Integer> stack = new Stack<>();
        while (curr != null) {
            stack.push(curr.val);
            curr = curr.next;
        }
        curr = head;
        while (!stack.empty() && curr != null) {
            if (stack.pop() != curr.val) {
                return false;
            }
            curr = curr.next;
        }
        return true;
    }
    
    public static void main(String[] args) {
        
        Node l1 = new Node(1);
        l1.next = new Node(2);
        l1.next.next = new Node(3);
        l1.next.next.next = new Node(3);
        l1.next.next.next.next = new Node(2);
        l1.next.next.next.next.next = new Node(1);
        printList(l1);
        System.out.println(isPalindrome(l1));
        System.out.println("------");

        l1 = new Node(1);
        l1.next = new Node(2);
        l1.next.next = new Node(3);
        l1.next.next.next = new Node(2);
        l1.next.next.next.next = new Node(1);
        printList(l1);
        System.out.println(isPalindrome(l1));
        System.out.println("------");

        l1 = new Node(0);
        l1.next = new Node(2);
        l1.next.next = new Node(3);
        l1.next.next.next = new Node(3);
        l1.next.next.next.next = new Node(0);
        printList(l1);
        System.out.println(isPalindrome(l1));
        System.out.println("------");
        
        l1 = new Node(1);
        printList(l1);
        System.out.println(isPalindrome(l1));
    }
}

@@ -259,17 +259,16 @@
 .%0A     *
- 
 %0A     * 
@@ -526,16 +526,55 @@
 ck%3C%3E();%0A
+        // pop all elements into stack%0A
         
@@ -703,159 +703,1225 @@
     
-while (!stack.empty() && curr != null) %7B%0A            if (stack.pop() != curr.val) %7B%0A                return false;%0A            %7D%0A            curr = curr
+// as stack contains the elements in reverse order, pop and compare with the list one by one%0A        while (curr != null) %7B%0A            if (curr.val != stack.pop()) %7B%0A                return false;%0A            %7D%0A            curr = curr.next;%0A        %7D%0A        return true;%0A    %7D%0A%0A    /**%0A     * This is a similar approach like above but a bit faster as we are not iterating the entire list twice.%0A     *%0A     * @param head starting node of the linked list.%0A     * @return %7B@code true%7D if linked list palindrome, %7B@code false%7D otherwise.%0A     */%0A    private static boolean isPalindromeOptimized(Node head) %7B%0A        Node slow = head;%0A        Node fast = head;%0A        Stack%3CInteger%3E stack = new Stack%3C%3E();%0A%0A        // push half of the elements into the stack%0A        while (fast != null && fast.next != null) %7B%0A            stack.push(slow.val);%0A            slow = slow.next;%0A            fast = fast.next.next;%0A        %7D%0A%0A        // linked list has odd number of elements, so forward the slow reference by one%0A        if (fast != null) %7B%0A            slow = slow.next;%0A        %7D%0A%0A        while (slow != null) %7B%0A            if (slow.val != stack.pop()) %7B%0A                return false;%0A            %7D%0A            slow = slow
 .nex
@@ -1960,20 +1960,16 @@
 ;%0A    %7D%0A
-    
 %0A    pub
@@ -2006,24 +2006,16 @@
 args) %7B%0A
-        
 %0A       
@@ -2304,32 +2304,87 @@
 alindrome(l1));%0A
+        System.out.println(isPalindromeOptimized(l1));%0A
         System.o
@@ -2647,32 +2647,87 @@
 alindrome(l1));%0A
+        System.out.println(isPalindromeOptimized(l1));%0A
         System.o
@@ -2990,32 +2990,87 @@
 alindrome(l1));%0A
+        System.out.println(isPalindromeOptimized(l1));%0A
         System.o
@@ -3091,24 +3091,16 @@
 ----%22);%0A
-        
 %0A       
@@ -3183,20 +3183,76 @@
 drome(l1));%0A
+        System.out.println(isPalindromeOptimized(l1));%0A%0A
     %7D%0A%7D%0A

Palindrome linkedlist: done