Finding palindromes in a linked list

Question

This is an interview question(again).

Given a singly connected linked list, find the largest palindrome in the list. (You may assume the length of the palindrome is even)

The first approach I made was using a stack - we traverse over the list from the start and keep pushing in the letters. Whenever we find the letter on the top of the stack is same as the next letter on the linked list, start popping(and incrementing the linked list pointer) and set a count on the number of letters that matches. After we find a mismatch, push back all the letters that you popped from the stack, and continue your pushing and popping operations. The worst case complexity of this method would be O(n2) e.g. when the linked list is just a string of the same letters.

To improve on the space and time complexity(by some constant factors), I proposed copying the linked list to an array and finding the largest sized palindrome in the array which again takes O(n2) time complexity and O(n) space complexity.

Any better approach to help me with? :(

Answer 1

One could come up with a O(n²)-algorithm with O(1) space complexity as follows:

Consider f→o→b→a→r→r→a→b:

Walk through the list reversing the links while visiting. Start with x=f and y=f.next:

• set x.next = null

• f o→b→a→r→r→a→b
  ^ ^
  |  \
  x   y

  and check for how many links both lists (x and y) are equal.
• Now continue. (tmp=y.next, y.next=x, x=y, y=tmp) E.g. in the second step, it will yield f←o b→a→r→r→a→b, with x=o and y=b, now you check again if it's a palindrome and continue:
• f←o←b a→r→r→a→b
• f←o←b←a r→r→a→b
• f←o←b←a←r r→a→b yay :)
• etc.

If you need to restore the list again, reverse it again in O(n)