单链表面试问题

我的解决方案是:快速和慢速的ptrs,将列表的一半反转,并与另一半进行比较。然后将颠倒的那一半倒过来,这样列表看起来就会像原来的一样。我正在寻找更好的解决方案。

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

以下应该在o(n)中执行。

1. 递归到列表末尾,保留头部指针。
2. 当退出递归循环时,将电流与磁头进行比较,然后将磁头移动到磁头上。接下来,直到字符用完或发现不匹配为止。

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

如果字符串中的字符数大于允许的最大堆栈深度,这将不起作用。在这种情况下,更改列表的工作方式如下…

找出列表的长度。

• 继续反向链接列表中的链接,直到到达中间… 一旦你到达中间,
• 你将有一半的列表指向开始,其余的则指向结束。
• 运行一个while循环直到结束,然后比较相应的字符并再次反转链接…

您可以使用随机化在O(n)时间和O(1)空间中完成它。

步骤1:计算字符串的散列值,例如整个字符串的指纹。

步骤2:反转链接列表。

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

步骤4:将链接列表反转为其原始顺序。

可以在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;
  }
}

把清单翻一遍,找出它的长度

然后您可以检查字符i==字符长度-i对于i=0到长度/2

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

这是一个蛮力算法,希望你能理解。

<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>

虽然\u指向的迭代器\的代码(请原谅我的糟糕命名)是:

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
}

根据他们告诉你的要求,这里有他们想要的解决方案。

1)找到列表的中点。您可以通过使用两个指针并增加两个节点和一个节点来实现这一点。当第一个指针到达末尾时,第二个指针将位于列表的中间节点。

2)将链接列表从中间反转到末尾。你可以在线性时间内做到这一点。

3)现在比较两个列表。

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

最好的方法是编写一个函数来在线性时间内反转列表,并将其用作ispaLindRome函数的助手。这将清除代码,并使在白板上管理更容易。

也许你可以做一个分而治之的解决方案:

1. 检查一次列表以确定其长度- O(n)
2. 再次浏览列表以将光标定位在半部分上-现在有光标A&B- o(n)

3. 比较A是否与B相反:

   • 如果左侧长度大于 一些常量,将a拆分为光标 a1和a2通过横移进行相同的操作 对于b1和b2- o(n) ;比较A1和 b2、a2和b1的方式相同

   • 如果左边的长度小于 一些恒定的,只是蛮力 比较它们-将b复制到数组中 把它倒过来比较一下 有一个- 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(对数) 因为递归调用,但这似乎没有违反任何约束。但是可以修改解决方案,使其不使用递归调用,而是使用循环-您应该只存储递归深度和该深度的位置(假设您已经绘制了递归树-您只需要两个整数来存储该树中的位置,以了解下一步是什么)。

这个看起来很酷。

假设您有一个链接列表node1->node2->node3->->noden。

设SUM1=SUM2=0

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

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

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

比较它们是否相等

如果相等

   palindrome 

其他的

   not a palindrome. 

时间复杂度:o(n)

空间复杂性:O(1)

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);