Wap to check whether the linked list is a palindrome or not
Given a singly linked list of characters, write a function that returns true if the given list is palindrome, else false. Show METHOD 1 (Use a Stack) Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.
To divide the list in two halves, method 2 of this post is used. C
Java
C#
Output:a->NULL Palindrome b->a->NULL Not Palindrome a->b->a->NULL Is Palindrome c->a->b->a->NULL Not Palindrome a->c->a->b->a->NULL Not Palindrome b->a->c->a->b->a->NULL Not Palindrome a->b->a->c->a->b->a->NULL Is Palindrome Time Complexity: O(n) METHOD 3 (Using Recursion) If both above conditions are true then return true. The idea is to use function call stack as container. Recursively traverse till the end of list. When we return from last NULL, we will be at last node. The last node to be compared with first node of list. In order to access first node of list, we need list head to be available in the last call of recursion. Hence we pass head also to the recursive function. If they both match we need to compare (2, n-2) nodes. Again when recursion falls back to (n-2)nd node, we need reference to 2nd node from head. We advance the head pointer in previous call, to refer to next node in the list. However, the trick in identifying double pointer. Passing single pointer is as good as pass-by-value, and we will pass the same pointer again and again. We need to pass the address of head pointer for reflecting the changes in parent recursive calls. Thanks to Sharad Chandra for suggesting this approach. C
Java
Output:a->NULL Not Palindrome b->a->NULL Not Palindrome a->b->a->NULL Is Palindrome c->a->b->a->NULL Not Palindrome a->c->a->b->a->NULL Not Palindrome b->a->c->a->b->a->NULL Not Palindrome a->b->a->c->a->b->a->NULL Is Palindrome Time Complexity: O(n) Please comment if you find any bug in the programs/algorithms or a better way to do the same. |