Checking if a singly linked list is a palindrome.

Q. Implement a function to check if a linked list is a palindrome.

Method #1
Reverse the list and match half of the nodes with the nodes of the given list.

Method #2
Use a stack as described in the algorithm.

Algorithm:

1. Find the length of the linked list.
2. Put first half of the linked list in a stack.
3. Now from the beginning of the second half, check if the content popped from the stack is the same as the current node in the second half advancing to the end.
4. Take care to see if the length of the list is odd, the beginning of the second list is from size/2+1th index.

Method #3
Use recursion.

Source (Method 2 and 3):

import java.util.Stack;

class Pair{
        LinkedList.Node node;
        boolean equal;
        
        Pair(LinkedList.Node node, boolean equal){
            this.node = node;
            this.equal = equal;
        }
}

public class Code{ 
    
    //Recursive solution
    static Pair check(LinkedList.Node node, int length){ 
        if(length == 1) return new Pair(node.next, true);
        else if(length==0)return new Pair(node, true);
        Pair r = check(node.next, length-2);
        if(r.node == null)return r;
        if(r.equal){
            System.out.println("*Recursive*: Comparing "+r.node+" with "+node);
            if(r.node.equals(node))return new Pair(r.node.next, true);
            else return new Pair(null, false);
        }
        return new Pair(null, false);
    }
    
    static boolean check(LinkedList ll){
        if(ll.head == null){System.out.println("Empty list");return false;}
        LinkedList.Node head = ll.head;
        int length = 0;
        while(head!=null){length++;head = head.next;}
        return check(ll.head, length).equal;
    }
    
    //Solution using a Stack
    public static <T> boolean checkPalindrome(LinkedList<T> ll){
        if(ll.head == null){System.out.println("Empty list");return false;}
        LinkedList.Node front = ll.head, t = ll.head;
        int s = 0, size = 0;
        while(t!=null){ size++; t = t.next; }
        
        t = ll.head;
        for(int i=0;i<size/2;++i) t = t.next; 
        if(size%2==1)t = t.next;
             
        Stack<T> stack = new Stack<>();
        
        while(t!=null){
            stack.push((T)t.value);
            t=t.next;
        }
        
        while(!stack.isEmpty()){
            if(!front.equals(stack.pop()))return false;
            else front = front.next;
        }
        return true;
    }
    
    
    
    public static void main(String[] args){
        Character[] a = {'c','o','d','e','z','e','d','o','c'};
        LinkedList<Character> ll = new LinkedList<>();
        for(char c:a)ll.add(c);
        System.out.println("Checking list : "+ll.toString());
        System.out.println("Using recursion: "+check(ll));
        System.out.println("Using stack: "+checkPalindrome(ll)+"\n");
        
        a = new Character[]{'c','o','d','e','d','x','c'};
        ll = new LinkedList<>();
        for(char c:a)ll.add(c);
        System.out.println("Checking list : "+ll.toString());
        System.out.println("Using recursion: "+check(ll));
        System.out.println("Using stack: "+checkPalindrome(ll)+"\n");
        
        a = new Character[]{'a', 'a'};
        ll = new LinkedList<>();
        for(char c:a)ll.add(c);
        System.out.println("Checking list : "+ll.toString());
        System.out.println("Using recursion: "+check(ll));
        System.out.println("Using stack: "+checkPalindrome(ll)+"\n"); 
        
        a = new Character[]{};
        ll = new LinkedList<>();
        for(char c:a)ll.add(c);
        System.out.println("Checking list : "+ll.toString());
        System.out.println("Using recursion: "+check(ll));
        System.out.println("Using stack: "+checkPalindrome(ll));
        
    }
}

//Linked List Class Code

public class LinkedList <T>{
    
    Node head;
    
    public class Node{
        Node next;
        T value;
        
        Node(T value){this.value = value;}
        Node(){} 
        
        @Override 
        public boolean equals(Object o){ 
            return this.hashCode() == o.hashCode();
        }
        
        @Override
        public int hashCode(){
            return value.hashCode();
        }
        
        @Override
        public String toString(){
            return value.toString();
        }
    }
    
    public void add(T value){
        if(head==null){head = new Node(value); return;}
        Node t = head;
        while(t.next!=null){t = t.next;}
        t.next = new Node(value); 
    }
    
    public boolean isEmpty(){
        return head==null;
    }
    
    @Override
    public String toString(){
        StringBuilder bf = new StringBuilder();
        Node t = head;
        if(head==null)return null;
        while(t!=null){
            bf.append(t.value).append(" -> ");
            t = t.next;
        }
        bf.delete(bf.length()-4, bf.length());
        return bf.toString();
    } 
}

Output:

Checking list : c -> o -> d -> e -> z -> e -> d -> o -> c
*Recursive*: Comparing e with e
*Recursive*: Comparing d with d
*Recursive*: Comparing o with o
*Recursive*: Comparing c with c
Using recursion: true
Using stack: true

Checking list : c -> o -> d -> e -> d -> x -> c
*Recursive*: Comparing d with d
*Recursive*: Comparing x with o
Using recursion: false
Using stack: false

Checking list : a -> a
*Recursive*: Comparing a with a
Using recursion: true
Using stack: true

Checking list : null
Empty list
Using recursion: false
Empty list
Using stack: false