单链表面试题

Question

假设我们有一个字符串：MALAYALAM，每个字符都是每个节点的数据部分，所以我们将有一个大小为 9 的列表。我们如何知道该列表是否是回文。

约束：

• 我们不知道列表长度。
• 不要对整个列表或一半列表使用临时内存（数组或堆栈或其他列表）。使用少量临时字符是可以接受的。
• 列表修改是可以的，只要我们在操作结束时有原始列表即可。

想到的解决办法不多，想和大家讨论一下。并且它是单链表。

谢谢&平均值， 〜卡尔文

Answer 1

我的解决方案：采用快速和慢速指针，反转列表的一半并与另一半进行比较。并将反转的一半反转，以便列表看起来像原始列表。我正在寻找更好的解决方案。

编辑：因为我找不到更好的溶胶。

Answer 2

下面应该在 O(n) 内完成

1. 递归到列表末尾，保留头指针。
2. 当退出递归循环时，将当前与头部进行比较，并将头部移动到 head.next ，直到用完字符或发现不匹配。

您可以通过记录列表的长度并在达到列表的一半后停止比较来改进此解决方案。

如果字符串中的字符数大于允许的最大堆栈深度，则此操作将不起作用。在这种情况下，更改列表将按如下方式进行...

找出列表的长度。

• 不断反转链接列表中的链接，直到到达中间......
  一旦你到达中间，
• 你将有一半的列表指向开始，其余的将指向结束。
• 运行 while 循环直到最后并比较相应的字符并再次反转链接......

Answer 3

您可以使用随机化在 O(n) 时间和 O(1) 空间内完成此操作。

步骤1：计算字符串的哈希值，例如整个字符串的指纹。

步骤2：反转链表。

步骤 3：计算反转字符串的哈希值。

第四步：将链表反转到原来的顺序。

反转链表可以在 O(n) 时间和 O(1) 空间内完成，如下所示：

rev(head) {
  prev = nil;
  curr = head;
  next = head.next;
  while (curr != nil) {
    curr.next = prev;
    prev = curr;
    curr = next;
    next = curr.next;
  }
}

Answer 4

遍历列表一次以找出其长度

，然后您可以检查字符 i == 字符长度 - i（i=0 到 length/2）是否

在 O(n^2) 时间内运行并使用 O(1) 存储

Answer 5

这是一个暴力算法，希望你能明白。

<pseudocode>

begin = list.begin();
end = list.end();

while (begin < end) {
   previous = iterator_that_points_to(list, end);
   if (*begin != *previous)
      return false;

   begin++;
   end = previous;
}
return true;

</pseudocode>

虽然 iterator_that_points_to 的代码（请原谅我的糟糕命名）是：

Node* iterator_that_points_to(CharList const& theList, Node* to_find)
{
   Node* iterator = theList.rootNode;
   while (iterator.next != 0) {
      if (iterator.next == to_find)
         return iterator;

      iterator = iterator->next; 
   }
   return 0; // should never happen
}

Answer 6

根据他们告诉您的要求，这是他们想要的解决方案。

1）找到列表的中点。您可以通过使用两个指针并增加两个节点，然后将第二个节点增加一个节点来完成此操作。当第一个指针到达末尾时，第二个指针将位于列表的中间节点。

2）将链表从中间翻转到末尾。您可以在线性时间内完成此操作。

3) 现在比较两个列表。

4) 通过再次反转来恢复之前反转的列表。

最好的想法是编写一个函数来在线性时间内反转列表，并将其用作 ispalindrome 函数的助手。这可以清理代码并使其更容易在白板上进行管理。

Answer 7

也许您可以采取分而治之的解决方案：

1. 遍历列表一次以确定其长度 - O(n)
2. 再次遍历列表以将光标定位在一半上 - 您现在有光标 A & ; B - O(n)

3. 比较 A 是否是 B 的逆：

   • 如果剩余长度大于
     一些常量，将 A 拆分为游标
     A1和A2通过遍历，同样操作
     对于 B1 和 B2 - O(n)；比较A1和
     B2，A2和B1同理

   • 如果剩余长度小于
     一些恒定的，只是蛮力
     比较它们 - 将 B 复制到数组中
     并向后阅读比较
     与 A - O(1)

请注意，步骤 3 应重复 O(logn) 次，因此，解决方案的复杂度为 O(nlogn)< /代码>。

更详细的复杂性分析：

f(const) = const

f(n) = f(n/2) + f(n/2) + C*n

使用代换 (n = 2^m, f(2^m) = g(m)) 来求解该方程。此递归的解决方案应该产生与 n*logn 相同复杂度类别的结果。

由于递归调用，空间复杂度为 O(logn)，但这似乎并没有违反任何约束。但是可以修改解决方案，使其不使用递归调用，而是使用循环 - 您应该只存储递归深度和该深度的位置（想象一下您绘制了递归树 - 您只需要 2 个整数来存储位置在那棵树上知道你的下一步是什么）。

Answer 8

这个看起来很酷。

假设您有一个链接列表 Node1->Node2->Node3->--->Noden。

让 sum1=sum2=0

你所要做的就是遍历一次列表并计算

           sum1 = (sum1+Nodei->data)*2.

           sum2 += Nodei->data*2^i.

并比较它们是否相等

if equal

   palindrome 

else

   not a palindrome. 

---

时间复杂度：O(n)

空间复杂度：O(1)

Answer 9

palindrome = true; //assume initially that it is a palindrome
count = 1;
q = p; // use a temporary pointer for traversing to end
while (q->next) { q = q->next; count ++; } //count the number of elements in the list
do{
   if (p->data != q->data) {palindrome = false; break;}//compare first and last elements of the list under consideration
   p = p->next; count -  = 2; //consider a new linked list with the two end-points cut off
   q = p; for (j = 0; j < count; j++) q = q=>next; 
} while (count > 0);