Jun 122012

Write a function to check if a Singly linked list is a palindrome or not. For example, the linked list

2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 | is a palindrome |

M -> A -> L -> A-> Y -> A -> L -> A -> M | is a palindrome |

2 -> 3 -> 4 -> 5 -> 4 -> 6 -> 2 | is NOT a palindrome |

K -> A -> M -> A -> L | is NOT a palindrome |

The function should take O(n) time in worst case.

### Solution:

**Method-1: Use Recursion**

You need to compare the first and last node in the first loop and then compress the list

Time Complexity: O(n^{2})

bool isPalindrome(Node* head) { return isPalindromeRec(&head, head); } bool isPalindromeRec(Node **l, Node *r) { if (!r) // terminating condition return true; // If the sublist is not palindrome then don't need to check further if (! isPalindromeRec(l, r->link) ) return false; bool flag = (r->data == (*l)->data); *l = (*l)->link; // Move l forward return flag; }

**Method-2: Use reverse method**

Step 1. Move to the middle of the list. Step 2. Reverse the second half Step 3. compare the first and reversed second half one node at a time, if they are same return true else return false. Step 4. Reverse the 2nd half again to get the original list.

Time Complexity: O(n)

Extra Space used: O(1)

### One Response to “Check if a linked list is palindrome”

Comments (1)

The method 2 is more efficient but not easy to implement.

Find our discussion and source code in Java for both approaches here http://www.capacode.com/data-structure/linked-list/check-linked-list-palindrome/