## Monday, 10 August 2015

### How to check whether linked list is palindrome or not?

Linked list a data structure used for storing collection of data. It has following properties:
• Successive elements are connected through reference(Pointer)
• Last Element stores NULL reference.
• Size is not fixed. Can dynamically grow.
• Only Forward traversing is possible, No Backward processing is allowed.
•  No wastage of memory.

Now we have to check whether given Linked List is palindrome or not?

Before solving the problem, lets first understand, what is palindrome?. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward

We can solve this problem by following approaches:
1. Using Stack(Iterative way or Recursive Way(internally uses stack))
1. Push all the elements into stack.
2. Pop the element from stack and compare with header of Linked List
3. If both the elements are same, then header to next node
4. Repeat the steps 2 & 3, until stack is empty and no more left in Linked List
2.  Without stack
1. First find the middle node of the node.
2. Reverse the second half.
3. Now compare Next pointer of middle with header,
4. If both are same then move to next pointer and compare.
5. Repeat step 2 &3 until it reaches to end of the linked list,

}

this.data = data;
}
private T data;

public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
return next;
}
this.next = next;
}
}

With Stack:

Recursive Way:

return true;
}
return true;
}
return false;
}
return false;
}

Iterative Way:

``` private boolean isPalindromeIterativeWay(LinkList<Integer> listHeader) {       Stack<LinkList<Integer>> stack=new Stack<LinkList<Integer>>();       LinkList<Integer> list=listHeader;      while(list!=null){           stack.push(list);           list=list.getNext();        }      while(listHeader!=null){           LinkList<Integer> list=stack.pop();           if(list.getData()!=listHeader.getData()){                 return false;           }              listHeader=listHeader.getNext();      } return true; }```

Without Stack:
``` private boolean isPalindrome1(LinkList<Integer> root) {         LinkList<Integer> middleNode = middleNode(root);         LinkList<Integer> middleNext = reverse(middleNode.getNext());                 while (middleNext!=null) {             if (root.getData() != middleNext.getData()) {                 return false;             }             root = root.getNext();             middleNext = middleNext.getNext();         }         return true;     } ```

I'll post Middle Node and reverse function in separate post.