Linked List Palindrom

1. Node.java

 package com.nrs.ds.basic.ll.ex;  
 public class Node {  
      char data;  
      Node next;  
      Node (char d){  
           data = d;  
           next = null;  
      }  
 }

2.  LinkedListPalindromImpl.java
 package com.nrs.ds.basic.ll.ex;  
 public class LinkedListPalindromImpl {  
      Node head;  
      Node slow_ptr, fast_ptr, second_half;  
      boolean isPalindrome(Node head){  
           slow_ptr = head;   
           fast_ptr = head;  
           Node prev_of_slow_ptr = head;  
           Node midnode = null;  
           boolean result = true;  
           if( head != null && head.next != null){  
                while( fast_ptr != null && fast_ptr.next != null){  
                     fast_ptr = fast_ptr.next.next;  
                     prev_of_slow_ptr = slow_ptr;  
                     slow_ptr = slow_ptr.next;  
                }  
                if(fast_ptr != null){  
                     midnode = slow_ptr;  
                     slow_ptr = slow_ptr.next;  
                }  
                second_half = slow_ptr;  
                prev_of_slow_ptr.next = null;  
                reverse();  
                result=compareLists(head, second_half);  
                reverse();  
                if(midnode != null){  
                     prev_of_slow_ptr.next = midnode;  
                     midnode.next = second_half;  
                }else{  
                     prev_of_slow_ptr.next = second_half;  
                }  
           }  
           return result;  
      }  
      void reverse(){  
           Node prev = null;  
           Node current = second_half;  
           Node next;  
           while( current !=null){  
                next = current.next;  
                current.next = prev;  
                prev = current;  
                current = next;  
           }  
           second_half = prev;  
      }  
      public boolean compareLists(Node head1, Node head2){  
           Node temp1 = head1;  
           Node temp2 = head2;  
           while(temp1 != null && temp2 != null){  
                if(temp1.data == temp2.data){  
                     temp1 = temp1.next;  
                     temp2 = temp2.next;  
                }else  
                     return false;  
           }  
           if(temp1 == null && temp2 == null)  
                return true;  
           return false;  
      }  
      public void push(char new_data){  
           Node new_node = new Node(new_data);  
           new_node.next = head;  
           head = new_node;  
      }  
      public void printList(Node ptr){  
           while(ptr != null){  
                System.out.print(ptr.data + "->");  
                ptr = ptr.next;  
           }  
           System.out.println("NULL");  
      }  
 }
3. Test
 package com.nrs.ds.basic.ll.ex;  
 public class LinkedListPalindromTest {  
      public static void main(String[] args) {  
           LinkedListPalindromImpl lp = new LinkedListPalindromImpl();  
           char str[] = {'M','A','D','A','M'};  
           String string= new String(str);  
           for(int i=0; i<str.length;i++){  
                lp.push(str[i]);  
                lp.printList(lp.head);  
                if(lp.isPalindrome(lp.head) != false){  
                     System.out.println("Is Palindrome");  
                     System.out.println("");  
                }else{  
                     System.out.println("Not Palindrome");  
                     System.out.println("");  
                }  
           }  
      }  
 }
Output:

Comments

Post a Comment

Popular posts from this blog

Tournament Tree or Winner Tree

Image
Tournament Tree or Winner Tree :  Is a form of min(max) heap which is a complete binary tree. every external node represents a player and internal node represents a winner. Winner: select the best player among N palyers , (N -1) players to be eliminated. we need minimum of (N-1) games (comparisons). Second best player: we can pick second best player in (N + log2(n-2)) comparisons.   The above tree contains 4 leaf nodes that represent players and have 3 levels 0, 1 and 2. Initially 2 games are conducted at level 2, one between 5 and 3 and another one between 7 and 8. In the next move, one more game is conducted between 5 and 8 to conclude the final winner. Overall we need 3 comparisons. For second best player we need to trace the candidates participated with final winner, that leads to 7 as second best. Uses: Tree selection sort using tournament tree.  
Read more

Linked List

Image
single linked list: 1. Node class NodeLL.java package com.nrs.ds.basic; public class NodeLL { Object value; NodeLL next; public NodeLL(Object value,NodeLL next){ this.value=value; this.next = next; } } 2. LinkedList implementation LinkedListImpl.java package com.nrs.ds.basic; public class LinkedListImpl<T> { NodeLL head; public LinkedListImpl(){ head = null; } public void add(Object value){ NodeLL newNode= new NodeLL(value,null); if(head == null){ head=newNode; }else{ newNode.next = head; head = newNode; } } public void delete(){ head = head.next; } public void display(){ NodeLL n=head; while(n != null){ System.out.println((T)n.value); n = n.next; } } ...
Read more

Heaps

Image
 A Binary Heap is either Min Heap or Max Heap. Min Binary Heap: the key at root must be minimum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree. Min Binary Heap: The key at root must be maximum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree. Binamial Heap: Binamial Heap  is a Extention of Binary Heap that provides faster union or merge operations together with other operations provided by Binary Heap. Is a collection of tinomial trees. Binamial Tree Tree: A binomial Tree of order 0 has 1 node. A binomial Tree oder k can be constructed by taking two binomial trees of order k-1, and making one as leftmost child of other.  Binomial Heap: Is a set of Binomial Tree where each Binomial Tree follows Min Heap Property. and there can be at-most one Binomial Tree of any degree. Fibonacci Heap:  In terms of Time Com...
Read more