21 Nov 2013

Linked List: Palindrome Linked List

Problem Statement : 
          Check if the given Linked List is a Palindrome or not.

Example of Palindrome Linked List


Solution:

To run the source code: LINK

The structure of the Node in the linked List :

 -/**
 * Linked List Node
 * @author Prateek
 */
class Node {
 public int data;
 public Node next;
 public Node(int data){
  this.data=data;
 }
 public String toString(){
  return ""+data;
 }
}-

Implementation of the Logic to check if linked list is Pallindrome

- /**
 * To check if Linked list is pallindrome or not
 * @author Prateek
 */
public class LinkListPallindrome {
 
 public boolean checkPallindrome(Node head){
  Node n =isPallindrome(head,head);
  if(n==null)
   return false;
  return true;
 }
 
 public Node isPallindrome(Node head , Node curr){
  
  if(curr == null)
   return head;
  
  Node rval = isPallindrome(head, curr.next);
  
  if(rval!=null)
   if(rval.data == curr.data)
    return rval = (rval.next!=null) ? rval.next : rval;
  
  return null ;
 }
 
 public static void main(String[] args) {
  
  Node head= new Node(1);
  head.next= new Node(2);
  head.next.next= new Node(3);
  head.next.next.next= new Node(2);
  head.next.next.next.next= new Node(2);
  
  LinkListPallindrome obj = new LinkListPallindrome();
  System.out.println(obj.checkPallindrome(head));
 }
}-

Time Complexity: O(n)
Space Complexity: O(n)

Please post your suggestion if any improvisation in the code is possible, would be happy to hear from you , please comment.

Happy Coding!!

No comments:

Post a Comment