To check palindrome in LinkedList -comparing linkedList and Reverse LinkedList.Getting incorrect answer?

Question

public class CheckPalindromeLL {

    public static void main(String args[])
    {
        Link head=null;

        Link l1=createLinkList1(head);
        Link l2=l1;
        System.out.println("first linklist");
        display(l1);

        System.out.println("reveresed linklist");
        Link rev=reverse(l1);
        Link rev2=rev;
        display(rev2);
        System.out.println("IS PALINDROME");
        compare(l1,rev);
    }

    private static  Link reverse(Link l11) {
        Link l12=l11;
        // TODO Auto-generated method stub
        Link nextp;
        Link curr=l12;
        Link prevp=null;
        while(curr!=null)
        {
            nextp=curr.next;
            curr.next=prevp;
            prevp=curr;
            curr=nextp;
        }

        return prevp;
    }

    private static  boolean compare(Link d1, Link d2) {

        boolean flag=true;
        while((d1!=null) && (d2!=null)&& flag)
        {
            if(d1.num!=d2.num)
            { System.out.println("not same ");
                flag=false;
                break;
            } 
            else
            {
                System.out.println("list:"+d1.num);
                System.out.println("rev:"+d2.num);
                System.out.println(" same");
                d1=d1.next;
                d2=d2.next;
            }
        }

        System.out.println("printing flag"+flag);
        return flag;
    }

    private static  Link createLinkList1(Link head) {
        // TODO Auto-generated method stub
        Link firstlink=head;
        Link newLink = null;

        Scanner reader = new Scanner(System.in); 
        System.out.println("Enter a number: ");
        int x[]={1,2,3,1};
        for(int i=0;i<x.length;i++)
        {
            newLink=new Link(x[i]);
            newLink.next=firstlink;
            firstlink=newLink;
        }
        head= firstlink;
        return newLink;
    }

    public static  void display(Link start)
    { 
        Link s1=start;
        while(s1!=null)
        {
            System.out.println(s1.num);
            s1=s1.next;
        }
    }
}

Comparing linkedlist and reverse of linkedlist but cannot compare second element.It just check first element of original and reverse linkedlist and give answer on the basis of first element only.Am i missing something??

Answer 1

In order to check if a LinkedList is palindrome you can use the following code:

Note that java.util.LinkedList is a doubly linked list.

public class Palindrome<T extends Comparable>{
    public boolean isPalindrome(LinkedList<T> list){
        Iterator<T> iterator = list.iterator();
        Iterator<T> reverseIterator = list.descendingIterator();
        while(iterator.hasNext()&&reverseIterator.hasNext()){
            if(!iterator.next().equals(reverseIterator.next())){
                return false;
            }
        }
        return true;
    }
}

Answer 2

You need to create a complete copy of the original list - in reverse order. This should do the trick:

private static Link reverse(Link l)
{
    Link result = null;
    while(l != null)
    {
        Link ll = new Link(l.value);
        ll.next = result;
        result = ll;
        l = l.next;
    }
    return result;
}

Just as addition: If you have a doubly linked list (for the case you are willing to adapt your implementation...), you can easily check for palindromes without creating a reversed copy:

private static boolean isPalindrome(Link head, Link tail)
{
    if(head == null)
    {
        return true; // arguable, if empty list is palindrome or not...
    }
    while(head != tail)
    {
        if(head.value != tail.value)
        {
            return false;
        }
        head = head.next;
        if(head == tail) // need this for even number of list elements
        {
            break;
        }
        tail = tail.previous;
    }
    return true;
}

EDIT Just a gimmick: Checking palindrome without duplicating the list (recursive):

private static boolean isPalindrome(Link head)
{
    return head == null ? true : isPalindrome(new Link[] { head }, head);
}
private static boolean isPalindrome(Link[] head, Link tail)
{
    if(tail.next != null)
    {
        if(!isPalindrome(head, tail.next))
        {
            return false;
        }
        head[0] = head[0].next;
    }
    return head[0].value == tail.value;
}

Answer 3

Here's an ASCII-art depiction of what your list (singular) looks like at each step. I've omitted the superfluous statements and print statements:

Link l1=createLinkList1(head);

       l1-+
          |
          V
          1 -> 2 -> 3 -> 1 -> null

Link rev=reverse(l1);

    rev------------------+
                         |
       l1-+              |
          |              |
          V              V
  null <- 1 <- 2 <- 3 <- 1

compare(l1,rev);

You only ever create one list and one set of nodes not two. When you reverse() it you rearrange the pointers but leave l1 pointing to what used to be the first element but is now the last one.