#CC150 #CC150-chap2 2.7 Implement a function to check if a linked list is a palindrome.

IsListPalindrome.java

package chap2;

import java.util.Stack;

//2.7  Implement a function to check if a linked list is a palindrome.
public class IsListPalindrome {

	/*
	 * Solution1: turn the list into an array then decide if the array is a
	 * palindrome. Trivial, not implemented here. Time O(n), Space O(n)
	 */

	/*
	 * Solution 2: Reverse the list, and compare the two lists to see if each
	 * value is the same. Not implemented here. Time O(n), Space O(n)
	 */

	/**
	 * Solution 3: Reverse the first half of the list with a stack. Use the
	 * stack to store the first half of the list, then compare each node in the
	 * second half with the top of the stack to see if they are all the same.
	 * 
	 * @return
	 */
	public static boolean isPalindromeWithStack(Node n) {
		if (n == null) {
			return false;
		}
		if (n.next == null) {
			return true;
		}
		// Use the runner technique to store the first half of the list. The
		// fast runner runs 2 steps at a time, the slow runner runs 1 step at a
		// time. When the fast runner reaches the end, the slow runner is at the
		// middle.
		Node fast = n;
		Node slow = n;
		Stack<Integer> stack = new Stack<Integer>();
		while (fast != null && fast.next != null) {
			stack.push(slow.data);
			slow = slow.next;
			fast = fast.next.next;
		}
		// If the list has odd number of elements, we skip the very middle
		// element
		if (fast != null) {
			slow = slow.next;
		}
		// Compare each following element in the list with each element in the
		// stack
		while (slow != null) {
			if (slow.data != stack.pop()) {
				return false;
			}
			slow = slow.next;
		}
		return true;
	}

	/**
	 * Solution 4: Use recursion, move from the middle through the nodes after
	 * it (back nodes) and compare it with the corresponding node in the front
	 * (front nodes). Use a wrapper class to wrap the front node to pass and the
	 * boolean value if they are the same.
	 * 
	 * Time: O(n), Space O(n) because of recursion
	 * 
	 * @param args
	 */
	public static boolean isPalindromeRecursive(Node n) {
		if (n == null) {
			return false;
		}
		if (n.next == null) {
			return true;
		}
		// Get the middle node with the runner technique
		Node slow = n;
		Node fast = n;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		// List has odd length, skip the middle node
		if (fast != null) {
			slow = slow.next;
		}
		// Now the slow pointer is at the beginning of the second half
		return isPalindromeRecursiveHelper(n, slow).isSame;
	}

	public static Result isPalindromeRecursiveHelper(Node head, Node backNode) {
		// Base case, we reach last node of the list
		if (backNode.next == null) {
			// Compare it with the head
			if (backNode.data == head.data) {
				return new Result(head.next, true);
			}
			return new Result(null, false);
		}
		// Recursive case
		Result res = isPalindromeRecursiveHelper(head, backNode.next);
		// Check if the previous comparison is already not the same
		if (!res.isSame||res.node==null) {
			return res;
		}
		// Do the comparison
		if (res.node.data == backNode.data) {
			// if it is the same, compare the next pair
			return new Result(res.node.next, true);
		}
		return new Result(null, false);
	}

	/**
	 * Solution 5: Same solution as in the book. Use recursion. Use an integer
	 * to keep track of if we have reached the middle. Use a wrapper class to
	 * pass back a boolean and a back node
	 * 
	 * @author heycinderella
	 * 
	 */

	public static Result isPalindromeRecursiveByLength(Node n, int length) {
		// Base case
		if (n == null || length == 0) {// The book returns true here, I think
										// this depends on the interviewer
			return new Result(null, false);
		} else if (length == 1) {
			// at the middle, the original list contains odd number of elements
			return new Result(n.next, true);
		} else if (length == 2) {
			// The original list contains even number of elements, compare the
			// middle, and return the node at the beginning of the second half
			return new Result(n.next.next, n.data == n.next.data);
		}
		// Recursive case
		Result res = isPalindromeRecursiveByLength(n.next, length - 2);
		// Do the comparison
		if (!res.isSame||res.node==null) {
			return res;
		}
		return new Result(res.node.next, n.data == res.node.data);

	}

	public static class Result {
		Node node;
		boolean isSame;

		public Result(Node n, boolean isSame) {
			this.node = n;
			this.isSame = isSame;
		}
	}

	public static void main(String[] args) {

		IsListPalindrome.Node n = new Node(1);
		n.appendToTail(2);
		n.appendToTail(3);
		n.appendToTail(1);

		System.out.println(isPalindromeRecursiveByLength(n, n.length()).isSame);

	}

	/**
	 * Implementation of a simple LinkedList
	 * 
	 * @author xl16
	 * 
	 */
	static class Node {
		Node next = null;
		int data;

		public Node(int d) {
			data = d;
		}

		public int length() {
			int len = 0;
			Node n = this;
			while (n != null) {
				len += 1;
				n = n.next;
			}
			return len;
		}

		public void appendToTail(int d) {
			Node end = new Node(d);
			Node n = this;
			while (n.next != null) {
				n = n.next;
			}
			n.next = end;
		}

		public String toString() {
			Node n = this;
			String str = "";
			while (n.next != null) {
				str += String.valueOf(n.data) + "->";
				n = n.next;
			}
			// The last node
			str += String.valueOf(n.data) + "->null";
			return str;
		}
	}

}