超难面试题，跪求答案。在线等
一美资公司上机题目。
设计一个链表，要求插入和删除的时间复杂度为O(1)。而且不能使用哈西。那位高人指点一下。
[解决办法]
二叉树?
[解决办法]
原题就这样
[解决办法]
复杂度为O(1)?
[解决办法]
是用数组模拟连表吧
[解决办法]
用静态链表怎么样
[解决办法]
仅供参考
struct Node
{
Tdata;
Node* next;
};
struct List
{
Node * pHead, * pTail;
};
void Insert (List & list, Node * pNode)
{
if (pHead == NULL)
{
pTail = new Node;//pTail是一个“空”节点
pHead = pNode;
pHead-> next = pTail;
}
else
{
pNode-> next = pHead-> next;
pHead = pNode;
}
}
void Delete (List & list, Node * pNode)
{
if (pNode-> next == pTail)
{
delete pTail;
pTail = pNode;
}
else
{
Node * tmp = pNode-> next;
pNode-> data = tmp-> data;
pNode-> next = tmp-> next;
delete tmp;
}
}
[解决办法]
正如lz所说，要实现“数组的直接访问的优点和链表插入删除不需要移动元素的优点”，的确是“又当了婊子又立了牌坊”，也许还有更巧妙的方法，但这种方法肯定很复杂。。。
[解决办法]
呵呵。我觉的这是一种取巧的办法，可能不能达到面试公司的要求。这样子会被卡掉的。^_^
--------------------------------------------
这个问题以前讨论过，我提供的基本上是“标准”方法。lz不要把公司里的人想得有多高明，我以前就碰到过一个人，他问了这么个问题：一个单向链表，末节点的next域指向null，如何在O(1)的空间复杂度下判断这个链表是否存在环？
当然，很多人知道这个问题的答案，我也知道，但这不是面试官想要的答案，因为题目说了末节点的next域指向null，这个链表根本就tmd不可能有环
[解决办法]
这个能保证时间复杂度O（1）吗？
[解决办法]
好象题目一样诶 - -！
什么公司啊，最近这么猛找人？
[解决办法]
mark.....一时没有好的办法.....期待高手.....
[解决办法]
mark
[解决办法]
不用 hash 自己用个crc模拟，搞个空间复杂度O(n) 的～
时间、空间都O(1) 的查询删除……吃萝卜吃多了吧……
[解决办法]
什么链表这么厉害!
[解决办法]
mark
[解决办法]
学习
[解决办法]
插入和删除的时间复杂度为O(1)
问一下
这里“复杂度为O(1)”
是什么意思
[解决办法]
void dele(snode **head,snode *node)
{
if(node==(*head))
{
delete (*head);
(*head)=0;
}
else
{
//下面将头结点的值全copy到node结点
node-> data=(*head)-> data;
...
//然后将头结点前移一位,再删除原来头结点,
snode *p=(*head);
head=(*head)-> next;
delete p;
}
}
巧妙使用头结点.
------解决方案--------------------
有点小错
head=&((*head)-> next);
[解决办法]
UP!
学习中~
[解决办法]
题目是叫你删除特殊的节点,特殊的节点,要么是头节点,要么 是尾节点
它们删除,插入,当然就是O(1)
[解决办法]
其实这道题还要主要看怎么理解这个 delete a specific node 删除指定的结点,觉得有点模糊
这个结点是给出来比如就是结点p,还是需要查找,如果值为p的结点.如果是前者我觉得我的算法没问题,如果是后者估计O(1)时间内实现,还要等等高人
[解决办法]
个位牛人，小弟我初学数据结构，不太懂农民说的，这怎么实现o(1)啊，实在是让人无法现想像！
[解决办法]
md ,,,,,,,,,,,我被e文阴过,,,很模糊的东西.
[解决办法]
收藏了。。。
