在链表中查找回文

Question

这是一个面试问题(再次).

给定一个单独连接的链表,找到列表中最大的回文.(你可以假设回文的长度是均匀的)

我做的第一种方法是使用堆栈 - 我们从头开始遍历列表并继续推送字母.每当我们发现在堆栈的顶部的字母是一样的链表上的下一个字母,开始弹出(与增加链表指针),并设置上的匹配字母数的计数.找到不匹配后,推回从堆栈中弹出的所有字母,然后继续推送和弹出操作.这种方法的最坏情况复杂性是O(n2),例如当链表只是一个相同字母的字符串时.

为了改善空间和时间的复杂性(通过一些常数因素),我提出将链表复制到一个数组并找到数组中最大尺寸的回文,这再次需要O(n2)时间复杂度和O(n)空间复杂度.

有没有更好的方法来帮助我？:(

Answer 1

人们可以提出一个具有O(1)空间复杂度的O(n²)算法,如下所示:

考虑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)中再次将其反转

Answer 2

这是一个 O(n^2) 算法：

1. 将列表转换为双向链表

2. 要获得偶数长度的回文，您需要将两个相同的字母相邻。因此，迭代每一对相邻字母（其中 n-1 个），并且在每次迭代中，如果字母相同，则找到中间字母是这两个字母的最大回文。