algorithm - 在链表中查找回文

Question

这又是一道面试题。

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

我采用的第一种方法是使用堆栈 - 我们从头开始遍历列表并不断插入字母。每当我们发现堆栈顶部的字母与链表中的下一个字母相同时，就开始弹出(并递增链表指针)并设置匹配字母数的计数。在我们发现不匹配后，将您从堆栈中弹出的所有字母推回，并继续您的插入和弹出操作。此方法的最坏情况复杂度为 O(n2)，例如当链表只是一串相同字母的时候。

为了提高空间和时间复杂度(通过一些常数因子)，我建议将链表复制到数组中并在数组中找到最大的回文，这同样需要 O(n2) 时间复杂度和 O(n)空间复杂度。

有什么更好的方法可以帮助我吗？ :(

Answer 1

可以想出一个 O(n²) 空间复杂度为 O(1) 的算法，如下所示:

考虑f→o→b→a→r→r→a→b:

在访问时通过列表反转链接。从 x=f 和 y=f.next 开始:

• 设置x.next = null

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

  并检查两个列表(x 和 y)相等的链接数。
• 现在继续。 (tmp=y.next, y.next=x, x=y, y=tmp) 例如。在第二步中，它将产生 f←o b→a→r→r→a→b，其中 x=o 和 y=b，现在你再次检查它是否是回文并继续:
• f←o←b a→r→r→a→b
• f←o←b←a r→r→a→b
• f←o←b←a←r r→a→b 是的:)
• 等等

如果需要再次恢复链表，在O(n)内再次反转