a********r
发帖数: 218 | 1 bool deleteNode(node* head, node* nodeToBeDeleted)
要实现O(1)，怎么做？ |
U*****n
发帖数: 1321 | 2 建个Hash Map，{node: prevNode} |
l*******u
发帖数: 198 | 3 单链表？如果被删除的节点可能是最后一个的话O(1)做不到 |
x*****6
发帖数: 7 | 4 这就是脑筋急转弯，把next的value复制到当前，然后把next删了。 |
a********r
发帖数: 218 | 5 xinqi大牛，
M的中国牛人给我出的这道题。被他据了。到现在我觉得我题目还没搞清楚，总觉得要O
(N)先找到这个要删的node, 怎么能O(1)?你能提供一段 pseudocode 吗？谢谢。
一并回楼上的问题：对， 这是单链表
【在 x*****6 的大作中提到】
: 这就是脑筋急转弯，把next的value复制到当前，然后把next删了。
|
t*****n
发帖数: 2578 | 6 要删的node不是参数传给你了么？
要O
【在 a********r 的大作中提到】
: xinqi大牛，
: M的中国牛人给我出的这道题。被他据了。到现在我觉得我题目还没搞清楚，总觉得要O
: (N)先找到这个要删的node, 怎么能O(1)?你能提供一段 pseudocode 吗？谢谢。
: 一并回楼上的问题：对， 这是单链表
|
a********r
发帖数: 218 | 7 tfusion (雷熔)大牛，
是的，但我要先找到这个node在链表(head)里的位置，这个找的过程需要O(N)，对吗？
要么，我没有理解这个题目，能给个psudocode吗？
【在 t*****n 的大作中提到】
: 要删的node不是参数传给你了么？
:
: 要O
|
r*******k
发帖数: 1423 | 8 如果是最后一个节点呢？
【在 x*****6 的大作中提到】
: 这就是脑筋急转弯，把next的value复制到当前，然后把next删了。
|
t*****n
发帖数: 2578 | 9 look at xinqi16 's solution.
【在 a********r 的大作中提到】
: tfusion (雷熔)大牛，
: 是的，但我要先找到这个node在链表(head)里的位置，这个找的过程需要O(N)，对吗？
: 要么，我没有理解这个题目，能给个psudocode吗？
|
h****e
发帖数: 2125 | 10 “
auto next = nodeToDelete->next;
nodeToDelete->value = next->value;
nodeToDelete->next = next->next;
delete next;
”
这题就是中国人最喜欢的弯弯绕，nodeToDelete其实并没有被delete，delete的反而是
next。
【在 a********r 的大作中提到】
: tfusion (雷熔)大牛，
: 是的，但我要先找到这个node在链表(head)里的位置，这个找的过程需要O(N)，对吗？
: 要么，我没有理解这个题目，能给个psudocode吗？
|
|
|
p*****n
发帖数: 64 | 11 前面很多人问了，就是nodeToDelete为空，即要删除的是最后一个node，做不到O（1）
【在 h****e 的大作中提到】
: “
: auto next = nodeToDelete->next;
: nodeToDelete->value = next->value;
: nodeToDelete->next = next->next;
: delete next;
: ”
: 这题就是中国人最喜欢的弯弯绕，nodeToDelete其实并没有被delete，delete的反而是
: next。
|
h****e
发帖数: 2125 | 12 nodeToDelete为空，为啥代表要删除最后一个node？你家链表最后一个node为空？程序
开始时候check一下，为空立刻报错return就完了。
【在 p*****n 的大作中提到】
: 前面很多人问了，就是nodeToDelete为空，即要删除的是最后一个node，做不到O（1）
|
a********r
发帖数: 218 | 13 M的中国牛人说要我实现下面的function
bool deleteNode(node* head, node* nodeToBeDeleted)
看来传进来的node* head没啥用
【在 h****e 的大作中提到】
: “
: auto next = nodeToDelete->next;
: nodeToDelete->value = next->value;
: nodeToDelete->next = next->next;
: delete next;
: ”
: 这题就是中国人最喜欢的弯弯绕，nodeToDelete其实并没有被delete，delete的反而是
: next。
|
y****w
发帖数: 3747 | 14 head有用啊 你看现在它剩下了，而且你没解决尾节点的问题，那就是它呗。
把head删了 当前尾节点prompt成head。
但链表相当于有环了。next是空或head都是遍历到头。这相当于放松了一点前提条件。
另外 这个函数返回bool是啥逻辑？返回head才make sense
: M的中国牛人说要我实现下面的function
: bool deleteNode(node* head, node* nodeToBeDeleted)
: 看来传进来的node* head没啥用
【在 a********r 的大作中提到】
: M的中国牛人说要我实现下面的function
: bool deleteNode(node* head, node* nodeToBeDeleted)
: 看来传进来的node* head没啥用
|
M********t
发帖数: 5032 | 15 这个副作用很大吧
【在 x*****6 的大作中提到】
: 这就是脑筋急转弯，把next的value复制到当前，然后把next删了。
|
h****e
发帖数: 2125 | 16 啰啰嗦嗦这么多，你还是没看懂solution。删的是next，从来不是head。
【在 y****w 的大作中提到】
: head有用啊 你看现在它剩下了，而且你没解决尾节点的问题，那就是它呗。
: 把head删了 当前尾节点prompt成head。
: 但链表相当于有环了。next是空或head都是遍历到头。这相当于放松了一点前提条件。
: 另外 这个函数返回bool是啥逻辑？返回head才make sense
:
:
: M的中国牛人说要我实现下面的function
:
: bool deleteNode(node* head, node* nodeToBeDeleted)
:
: 看来传进来的node* head没啥用
:
|
y****w
发帖数: 3747 | 17 好牛逼啊
【在 h****e 的大作中提到】
: 啰啰嗦嗦这么多，你还是没看懂solution。删的是next，从来不是head。
|
h**6
发帖数: 4160 | 18 没看懂的是你吧，如果nodeToDelete是tail，那么可以把head复制到tail，然后head删
除，这样形成一个循环链表。
【在 h****e 的大作中提到】
: 啰啰嗦嗦这么多，你还是没看懂solution。删的是next，从来不是head。
|
x*****6
发帖数: 7 | 19 恩你说得对，应该这样
if last node ：O(N)
else：O(1)
然后提及假设这个函数被调用的node to delete是均匀分布，可以认为整体是
amortized O(1)..
面试反正言之有理即可。。如果对方纠结这些也没意思
【在 r*******k 的大作中提到】
: 如果是最后一个节点呢？
|
x*****6
发帖数: 7 | 20 恩你说得对，应该这样
if last node ：O(N)
else：O(1)
然后提及假设这个函数被调用的node to delete是均匀分布，可以认为整体是
amortized O(1)..
面试反正言之有理即可。。如果对方纠结这些也没意思
【在 r*******k 的大作中提到】
: 如果是最后一个节点呢？
|
|
|
k***e
发帖数: 1931 | 21 把head的值复制到nodeToBeDeleted，然后返回head->next？
【在 a********r 的大作中提到】
: M的中国牛人说要我实现下面的function
: bool deleteNode(node* head, node* nodeToBeDeleted)
: 看来传进来的node* head没啥用
|
J********n
发帖数: 536 | 22 一看就知道出这题的是老中。出这种题，你想考察啥呢？
我前一阵子参加了几十场debrief，见了好多傻逼老中面试官和candidate，那天抽空写
写。
要O
【在 a********r 的大作中提到】
: xinqi大牛，
: M的中国牛人给我出的这道题。被他据了。到现在我觉得我题目还没搞清楚，总觉得要O
: (N)先找到这个要删的node, 怎么能O(1)?你能提供一段 pseudocode 吗？谢谢。
: 一并回楼上的问题：对， 这是单链表
|
N****2
发帖数: 531 | 23 xjbc，老子刚被烙印考了这道题
【在 J********n 的大作中提到】
: 一看就知道出这题的是老中。出这种题，你想考察啥呢？
: 我前一阵子参加了几十场debrief，见了好多傻逼老中面试官和candidate，那天抽空写
: 写。
:
: 要O
|
k***e
发帖数: 1931 | 24 想放水。
【在 J********n 的大作中提到】
: 一看就知道出这题的是老中。出这种题，你想考察啥呢？
: 我前一阵子参加了几十场debrief，见了好多傻逼老中面试官和candidate，那天抽空写
: 写。
:
: 要O
|
