## Thursday, December 25, 2014

### 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{
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);
}

int length = 0;
}

//Solution using a Stack
public static <T> boolean checkPalindrome(LinkedList<T> ll){
int s = 0, size = 0;
while(t!=null){ size++; t = t.next; }

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'};
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'};
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'};
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[]{};
System.out.println("Checking list : "+ll.toString());
System.out.println("Using recursion: "+check(ll));
System.out.println("Using stack: "+checkPalindrome(ll));

}
}

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();
}
}

while(t.next!=null){t = t.next;}
t.next = new Node(value);
}

public boolean isEmpty(){
}

@Override
public String toString(){
StringBuilder bf = new StringBuilder();
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