c***2
发帖数: 838 | 1 Remove a node from a singly linkedlist without knowing the head node. All
you have is the node itself. |
h***o
发帖数: 2321 | 2 please understand what is "a" node
this is tricky
【在 c***2 的大作中提到】
: Remove a node from a singly linkedlist without knowing the head node. All
: you have is the node itself.
|
d**e
发帖数: 6098 | 3 re这个，我觉得不行
【在 h***o 的大作中提到】
: please understand what is "a" node
: this is tricky
|
c***2
发帖数: 838 | 4 1) Try to run it, got infinite loop with random addresses
2) This is a wrong question |
c***2
发帖数: 838 | 5 This is not in an interview, if you know the trick, spit it out.
【在 h***o 的大作中提到】
: please understand what is "a" node
: this is tricky
|
d**e
发帖数: 6098 | 6 because that node is not really deleted.
you made a trick to simply modify the value inside that node and delete its
next node. from the outside, if you retrieve the value information, it looks
like the node was deleted. But actually, it is not.
if we have such case: |
c***2
发帖数: 838 | 7 Yes, that's definitely right.
But over here, we don't have access to p;
How to set it to NULL?
Suppose
p->next=q
free(q);
q=NULL;
this won't set p->next to NULL.
I am really confused.
I only use C, can any other lanuague support this feature?
its
looks
【在 d**e 的大作中提到】
: because that node is not really deleted.
: you made a trick to simply modify the value inside that node and delete its
: next node. from the outside, if you retrieve the value information, it looks
: like the node was deleted. But actually, it is not.
: if we have such case:
|
c***n
发帖数: 809 | 8 remember the previous one,
set the previous->next = cur-> next,
delete cur
【在 c***2 的大作中提到】
: Remove a node from a singly linkedlist without knowing the head node. All
: you have is the node itself.
|
|
l*****a
发帖数: 14598 | 9 if it is the last node of the linked list
you can only start from the beginning.
u need to know the head.otherwise u can't solve this problem.
for time complexity,
(n-1 * 1 +1 *n-1)/n=O(1)
【在 c***2 的大作中提到】
: Yes, that's definitely right.
: But over here, we don't have access to p;
: How to set it to NULL?
: Suppose
: p->next=q
: free(q);
: q=NULL;
: this won't set p->next to NULL.
: I am really confused.
: I only use C, can any other lanuague support this feature?
|
l*****v
发帖数: 498 | 10 sentinel
【在 c***2 的大作中提到】
: Remove a node from a singly linkedlist without knowing the head node. All
: you have is the node itself.
|
|
|
c***2
发帖数: 838 | 11 The question shall be modified as "delete a *middle* node". |
l*****a
发帖数: 14598 | 12 Don't u think that is a hint?
【在 c***2 的大作中提到】
: The question shall be modified as "delete a *middle* node".
|
c***2
发帖数: 838 | 13 otherwise, there is no solution for the last node. AN dturns this question
invalid. |
l*****v
发帖数: 498 | 14 sentinel node
【在 c***2 的大作中提到】
: otherwise, there is no solution for the last node. AN dturns this question
: invalid.
|
c***2
发帖数: 838 | 15 A dummy tail node.
that works.
free(node);
node=tail;
when traverse: while(p) ==> while(p!=tail).
But this does not comply with the question: "All
you have is the node itself." :-) |
l*****v
发帖数: 498 | 16 with senitel tail node, you don't have special case for last node. Here is
modification of your original code
boolean removeNode(Node * p){
Node * temp;
if (NULL == p){
return FALSE;
}
temp = p.next;
p.value = temp.value;
p.next = temp.next;
free(temp);
return TRUE;
} |
c***2
发帖数: 838 | 17 Finally got it: with a fixed dummy tail node, there is NO last node.
Thanks, |
