是否可以在不使用额外内存的情况下以 Θ(n) 时间复杂度检查单向链表是否是回文? [英] Is it possible to check if a singly linked list is a palindrome or not at Θ(n) time complexity without using extra memory?

问题描述

我刚刚参加了实习的在线面试，问题是检查单向链表是否是回文.我使用了一些内存来存储链表的数据.有人问我是否可以编写不使用额外内存的代码.我说可能需要超过 Θ(n) 即 Θ(n²).

I just attended an online interview for an internship and the question was to check if a singly linked list is a palindrome or not. I used some memory to store the data of the linked list. I was asked if I can write a code which doesn't use extra memory. I said it might take more than Θ(n) ie Θ(n²).

对话过去了，最终归结为以下内容:检查单向链表是否是回文在Θ(n)时间，同时不使用额外的内存，条件是<强>输入数据不受干扰.
我告诉这是不可能的，但我被告知它实际上是并且我应该在互联网上查找.但在我看到的所有算法中，至少有一个违反了这些条件，我个人认为这也是不可能的.

Conversation went by and it finally came down to the following: check whether a singly linked list is a palindrome or not in Θ(n) time all while not using extra memory with the condition that the input data is left undisturbed.
I told it was not possible but I was told it actually is and that I should look it up over the internet. But of all the algorithms I saw, at least one of these conditions are violated and I personally feel it is not possible too.

不使用额外的内存，我的意思是不使用 Θ(n) 内存.我们当然可以自由使用 Θ(1) 内存.

By not using extra memory, I mean not using Θ(n) memory. We are free to use Θ(1) memory of course.

所以，如果有人能消除这个疑问，提前致谢:D

So, if anyone can clear this doubt, thanks in advance :D

推荐答案

在列表可能被临时篡改的情况下，将其恢复到原始状态是可能的:

It is possible on the condition that the list may be temporarily tampered with, restoring it to its original state:

1. 扫描列表一次以计算元素的数量.
2. 使用该信息，再次扫描列表以找到列表后半部分的第一个元素.如果列表的长度为奇数，则这应该是中间元素之后.
3. 反转列表的后半部分.这可以使用额外的滞后和领先节点参考在线性时间内完成.请记住对最后一个节点的引用，该节点现在已成为反向列表后半部分的第一个节点.
4. 再次遍历列表，但现在同时遍历列表的后半部分.记住所有的比较是否匹配(所以它是一个回文)
5. 重复第 3 步恢复反转.
6. 返回第 4 步的结果

1. Scan the list once to count the number of elements.
2. Using that info, scan the list again to find the first element of the second half of the list. If the list has an odd length, this should be the element after the middle one.
3. Reverse that second half of the list. This can be done in linear time using an extra lagging and leading node reference. Remember the reference to the last node which now has become the first node of the reversed second half of the list.
4. Perform yet another traversal of the list, but now in tandem with a traversal over the reversed second half of the list. Remember whether all comparisons matched (so it is a palindrome)
5. Restore the reversal by repeating step 3.
6. Return the outcome of step 4

该算法不使用线性辅助空间，并在列表上执行固定次数的遍历，使其具有线性时间复杂度.

This algorithm uses no linear auxiliary space, and performs a fixed number of traversals over the list, giving it a linear time complexity.

这篇关于是否可以在不使用额外内存的情况下以 Θ(n) 时间复杂度检查单向链表是否是回文?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！