cc150_2.7

gistfile1.java

package cc150;
/*
 * 2.7 Implement a function to check if a linked list is a palindrome
 * Algorithm
 * 1, use slow and fast pointers ;
 * 2. slow move one step , fast move two steps
 * 3.fast reach the last node  the first reach the  central node
 * 4. create a new linked list , reverse to save the second half of the list
 * 5. compare two  lists from begin   until second list to end , 
 * 6. if the data doens't match , it is not  palindrome   
 * 
 * O(n) and O(n)
 * 
 * 
 */
public class CheckPalindrome {

	public static void main(String[] args) {
		PLNode root = new PLNode();
		root.chdata = 'A';
		PLNode current = root;
		PLNode newNode = new PLNode();
		newNode.chdata = 'B';
		current.next = newNode;
		current = current.next;
		
		newNode = new PLNode();
		newNode.chdata = 'C';
		current.next = newNode;
		current = current.next;

		newNode = new PLNode();
		newNode.chdata = 'D';
		current.next = newNode;
		current = current.next;
		
		newNode = new PLNode();
		newNode.chdata = 'E';
		current.next = newNode;
		current = current.next;
		
		newNode = new PLNode();
		newNode.chdata = 'D';
		current.next = newNode;
		current = current.next;
		
		newNode = new PLNode();
		newNode.chdata = 'C';
		current.next = newNode;
		current = current.next;

		newNode = new PLNode();
		newNode.chdata = 'B';
		current.next = newNode;
		current = current.next;
		newNode = new PLNode();
		newNode.chdata = 'A';
		current.next = newNode;
		boolean itis = isPalinDrome(root) ;
		if(itis)
			System.out.println("It is a PalinDrome");
		else
			System.out.println("Nope, It is not a palinDrome");
	}

	private static boolean isPalinDrome(PLNode root) {
		if(root == null || root.next == null)
			return false;
		PLNode slow = root;
		PLNode fast = root;
		while(fast!=null && fast.next!=null){
			slow = slow.next;
			fast = fast.next.next;
		}
		if(slow!=null){
			slow= slow.next;
			PLNode secondRoot = null;
			while(slow!=null){
				PLNode newNode = new PLNode();
				newNode.chdata = slow.chdata;
				newNode.next = secondRoot;
				secondRoot = newNode;
				slow = slow.next;
			}
			fast = root;
			while(secondRoot!=null){
				if(secondRoot.chdata != fast.chdata){
					return false;
				}
				secondRoot=secondRoot.next;
				fast = fast.next;
			}
		}
		return true;
	}

}

class PLNode {
	char chdata;
	PLNode next;

	public PLNode() {

	}
}