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


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){
 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);
   return false;
  return true;
 public Node isPallindrome(Node head , Node curr){
  if(curr == null)
   return head;
  Node rval = isPallindrome(head, curr.next);
   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();

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