234 Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

Example:

Picture a palindrom like:

0->1->2->1->0

Solution 1: Reverse and Compare

From the example we can see that, if the reverse linked list is identical to the original one, then it's palindrom

Note:

• When compare the linked list to the reverse list, we only need to compare the first half of the list

Solution 2: Iterative Approach

• Stack is a good data structure to accomplish this

  • Two ways to do this, depends on whether we know the size (length) of the linked list or not

    • if we know the size, standard loop through; but be careful the case when size is odd;

    • if we don't, use the fast/slow runner to find the midpoint of linked list by interating through it:

      • At each step in the loop, we push data from the slow runner into the stack. And then once the faster pointer hits the end of the list, the stack will have the first half of the linked list, but in reverse order
      • After that we simply iterate through the rest of linked list, and compare the node from the top of the stack at each iteration.

      • If we complete the iteration without finding a difference, then the linked list is a palindrome

        public boolean isPalindrome(ListNode head) {
          ListNode fast = head;
        ListNode slow = head;
        
        Stack<Integer> stack = new Stack<Integer>();
        
        /*
         * Push the first half of linked list into stack
         */
        while(fast != null && fast.next != null)
        {
            stack.push(slow.val);
            slow = slow.next;
            fast =  fast.next.next;
        }
        
        /*
         * If the list has odd number of elements, so skip the middle element
         * execute when fast.next == null
         */
        if(fast != null)
        {
            slow = slow.next;
        }    
        /*
         * 
         * continue iterate through the list after store the first half into stack
         */
        while(slow != null)
        {
            int top = stack.pop().intValue();
            if(top != slow.val)
            {
                return false;
            }
            slow = slow.next;
        }
        return true;
        }
        

Solution 3: Recursive Approach

We might have some intuitive idea that we want to compare element 0 and element n, element 1 and element n-1, and so on, until the middle element(s).

1. First we need to know when we've reach the middle element - we can do this by passing in length-2 for the length each time. When the length equal to 0 or 1, we're at the center of the linked list
2. Compare node i to node n-i to check if the linked list is panlindrome;

3. Still use stack - each call compares its head to returned_node, and then passes returned_node.next up to the stack:

   • Return values:
     1. If any point the values do not match return false;
     2. If the value match, it return that value.

4. A simple class to store two type of return values:

   class Result {
    public LinkedListNode node;
    public boolean result;
    }
   

   The return value will has both the node and the boolean value