Thursday, November 26, 2015

Check if a LinkedList is a Palindrome

Input:
LinkedList L = new LinkedList("HeleH");
L.printList();
System.out.println(L.isPalindrome());

Program:
import java.util.Stack;

public class LinkedList {
    int data;
    LinkedList next;
    private LinkedList(int data) {
        this.data=data;
        this.next=null;
    }
    public LinkedList(String data) {
        char[] a = data.toCharArray();
        int size=a.length;
        if(size>0)    {
            this.data=a[0];
            this.next=null;
            for(int i=1; i<size; i++)
                append(a[i]);
        }
    }
    public boolean isPalindrome()    {
        LinkedList L = this;
        Stack<Integer> S=new Stack<Integer>();
        LinkedList slow = L;
        LinkedList fast = L;
        while(fast!=null && fast.next!=null)    {
            S.push(slow.data);
            fast = fast.next.next;
            slow = slow.next;
        }
        boolean flag = true;
        if(fast!=null) //String has odd number of char
            slow = slow.next;
        while(slow!=null)    {
            if(slow.data!=S.pop())    {
                flag=false;
                break;
            }
            slow = slow.next;
        }
        return flag;
    }
    public void append(int data)    {
        LinkedList L = this;
        while(L.next!=null)
            L=L.next;
        L.next=new LinkedList(data);
    }
    public void printList()    {
        LinkedList L = this;
        StringBuffer sb = new StringBuffer();
        while(L!=null)    {
            sb.append((char)L.data);
            L=L.next;
        }
        System.out.println("String: "+sb.toString());
    }
}


This program also shows how to use an integer data linked list to store characters.

No comments:

Post a Comment

UA-39217154-2