H**********5
发帖数: 2012 | 1 今天onsite,
面某网络公司，
一轮技术聊天，问了下空间时间复杂度，问的很细，正好这个专题看过。秒过。
二轮笔记本上编程，
链表删除指定节点。C实现，
这个题如果写不出来，我真的可以钻地下了，
前几天还专门测试过。
然后在vim上编译通过，运行时，不可思议的一幕出现了，
总是assert失败，abort 6.
然后烙印让我把free注释掉试试，结果还是一样，
最后说,代码测试没有达到期望值。面试结束。
我可以肯定程序绝对是没有问题的。 |
H**********5
发帖数: 2012 | 2 测试程序是烙印自己题目中的测试用例，
用一个指针数组，每个元素是一个字符串形式的链表。
{
"1->2->3->4";
"2->3->3->4"
} |
l*********8
发帖数: 4642 | 3 要不你贴一下程序？
【在 H**********5 的大作中提到】
: 测试程序是烙印自己题目中的测试用例，
: 用一个指针数组，每个元素是一个字符串形式的链表。
: {
: "1->2->3->4";
: "2->3->3->4"
: }
|
H**********5
发帖数: 2012 | 4 void deleteNode(struct node *head,int data)
{
struct node *temp=NULL;
struct node *prev=head;
struct node *curr=head->next;
if(head->data==data)
{
if(head->next==NULL)
{
printf("There is only one node,can not be deletedn");
return;
}
head->data=head->next->data;
temp=head->next;
head->next=head->next->next;
free(temp);
return;
}
while(curr!=NULL)
{
if(curr->data==data)
{
prev->next=curr->next;
free(curr);
curr=prev->next;
}
else
{
prev=curr;
curr=curr->next;
}
}
}
前天在我电脑上跑过测试用例，没问题，
今天就奇了怪了，做过测过的原题，在烙印的环境下就报断言。
【在 l*********8 的大作中提到】
: 要不你贴一下程序？
|
m*****k
发帖数: 18 | 5 temp=head->next;
head->next=head->next->next;
free(temp);
you freed the head->next !!! are u sure u pasted the right program? |
H**********5
发帖数: 2012 | 6 temp=head->next;
head
1->2>3
head->next=head->next->next;
head
2->2->3
2->3
free(temp);
2->free(2)->3
any problem?
【在 m*****k 的大作中提到】
: temp=head->next;
: head->next=head->next->next;
: free(temp);
: you freed the head->next !!! are u sure u pasted the right program?
|
J**9
发帖数: 835 | 7 Also
1) what if head is NULL?
2) In case head->data == data: head got changed, did you reflect that |
J**9
发帖数: 835 | |
s***5
发帖数: 2136 | 9 very messy code with bugs.
for linked list related questions, you should always first check if a the "
head" is null or not.
it is not a special case when the head is the node you need to delete.
Node* deleteNode(Node *head, int data) {
if(head == NULL) return;
Node *dummy = new Node(0);
dummy->next = head;
Node *p = dummy;
while(p->next != NULL && p->next->val != data)
p = p->next;
if(p->next == NULL) return;
Node *tmp = p->next;
p->next = p->next->next;
delete tmp;
head = dummy->next;
delete dummy;
return head;
} |
s*****r
发帖数: 43070 | 10 code写的不够简洁，C程序还是很考基本功的，俺个人觉得比刷题有意义 |
|
|
z***b
发帖数: 127 | 11 struct node *deleteNode(struct node *head,int data)
{
if (head == NULL)
return NULL;
struct node temp;
temp.next = head;
struct node *prev = &temp, *curr = head;
while (curr != NULL) {
if (curr->data == data) {
struct node *deleted = curr;
prev->next = curr->next;
free(deleted);
curr = prev->next;
} esle {
prev = curr;
curr = curr->next;
}
}
return temp.next;
} |
z***b
发帖数: 127 | 12 楼主这个程序签名就不对.应该为
void deleteNode(struct node **head, int data);
或者
struct node *deleteNode(struct node *head, int data)； |
H**********5
发帖数: 2012 | 13 形参是被烙印写死的。
直接在函数体内编码。
【在 z***b 的大作中提到】
: 楼主这个程序签名就不对.应该为
: void deleteNode(struct node **head, int data);
: 或者
: struct node *deleteNode(struct node *head, int data)；
|
c****g
发帖数: 3893 | 14 我靠，现在的CS是不是都不教C了?
【在 z***b 的大作中提到】
: 楼主这个程序签名就不对.应该为
: void deleteNode(struct node **head, int data);
: 或者
: struct node *deleteNode(struct node *head, int data)；
|
z***b
发帖数: 127 | 15 你觉得烙印这个声明是对的？
http://geeksquiz.com/linked-list-set-3-deleting-node/
看看这个链接，可以想想烙印那个声明为啥不好。
【在 H**********5 的大作中提到】
: 形参是被烙印写死的。
: 直接在函数体内编码。
|
c****g
发帖数: 3893 | 16 估计老印的本意是想删掉中间的node，丫没说清楚
或故意不说清楚。LZ自己也是糊涂的，也没问个
明白。
看来以后面试要想废掉谁，就考C，现在的小盆友
们似乎都不学C了。
【在 z***b 的大作中提到】
: 你觉得烙印这个声明是对的？
: http://geeksquiz.com/linked-list-set-3-deleting-node/
: 看看这个链接，可以想想烙印那个声明为啥不好。
|
H**********5
发帖数: 2012 | 17 我晕，
果然烙印给的形参就是有问题的。
【在 z***b 的大作中提到】
: 你觉得烙印这个声明是对的？
: http://geeksquiz.com/linked-list-set-3-deleting-node/
: 看看这个链接，可以想想烙印那个声明为啥不好。
|
c****g
发帖数: 3893 | 18
你最好把人家的原话或条件一字不漏地post出来，
再想想有没有问题，问题在哪?
这些都是C最基本的trick.
【在 H**********5 的大作中提到】
: 我晕，
: 果然烙印给的形参就是有问题的。
|
n**d
发帖数: 26 | 19 话说这如果是空表上来访问head->data不就挂了么，这程序很难证实标题啊 |
s*****p
发帖数: 108 | 20 head->data=head->next->data;
这个看着也不对。 |
|
|
p****a
发帖数: 447 | 21 楼主前面head->next == null 返回了
反正楼主的code 比较不寻常
【在 s*****p 的大作中提到】
: head->data=head->next->data;
: 这个看着也不对。
|
h******o
发帖数: 30 | 22 面过老印。确实听不懂，确实总是challenge我。但是他只要觉得我答的还行，也不会
给太离谱的反馈的。 |
s*****p
发帖数: 108 | 23 不过如果烙印真是给了这个不寻常的函数签名，说不定真是想阴楼主。
【在 p****a 的大作中提到】
: 楼主前面head->next == null 返回了
: 反正楼主的code 比较不寻常
|
w******p
发帖数: 166 | 24 gcc 的运行环境是可以通过改变环境变量总给你个sigabrt，编译通过但是运行不了
但是出现这种问题的时候干瞪眼解决不了，如果有运行环境，可以用gdb运行一下看看
到底死在那儿了，最不济可以在源代码里写好多printf看看执行到哪儿了
我看你写的code确实考虑到了出题的前面，就是一不能处理空header指针，二如过前几
个node都需要删除的话只会删除第一个，但是用他给的那两个例子确实应该给出正确结
果，但是在他们的环境下还是有问题，那就考验你当场debug的能力啦 |
H**********5
发帖数: 2012 | 25 你的回复很有道理，
估计是烙印想整我，顺便审查下我调代码水平，但悲剧的是一直不是用的gdb调。
【在 w******p 的大作中提到】
: gcc 的运行环境是可以通过改变环境变量总给你个sigabrt，编译通过但是运行不了
: 但是出现这种问题的时候干瞪眼解决不了，如果有运行环境，可以用gdb运行一下看看
: 到底死在那儿了，最不济可以在源代码里写好多printf看看执行到哪儿了
: 我看你写的code确实考虑到了出题的前面，就是一不能处理空header指针，二如过前几
: 个node都需要删除的话只会删除第一个，但是用他给的那两个例子确实应该给出正确结
: 果，但是在他们的环境下还是有问题，那就考验你当场debug的能力啦
|
H**********5
发帖数: 2012 | 26 #include
#include
typedef struct node
{
int data;
struct node* next;
};
void printfList(struct node *head)
{
while(head!=NULL)
{
printf("%d-> ",head->data);
head=head->next;
}
printf("\n");
}
void pushAtBegin(struct node **head_ref,int data)
{
struct node *new_node=(struct node*)malloc(sizeof(struct node));
new_node->data=data;
new_node->next=*head_ref;
*head_ref=new_node;
}
void pushAtEnd(struct node **head_ref,int data)
{
struct node* temp=NULL;
struct node *new_node=(struct node*)malloc(sizeof(struct node));
new_node->data=data;
if(*head_ref==NULL)
{
*head_ref=new_node;
}
temp=*head_ref;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=new_node;
new_node->next=NULL;
}
void deleteNode(struct node **head,int data)
{
struct node *temp=NULL;
struct node *prev=(*head);
struct node *curr=(*head)->next;
if(NULL==(*head))
{
printf("No Node,failed to delete\n");
return;
}
if((*head)->data==data)
{
if((*head)->next==NULL)
{
printf("There is only one node,can not be deleted\n");
return;
}
(*head)->data=(*head)->next->data;
temp=(*head)->next;
(*head)->next=(*head)->next->next;
free(temp);
}
while(curr!=NULL)
{
if(curr->data==data)
{
prev->next=curr->next;
free(curr);
curr=prev->next;
}
else
{
prev=curr;
curr=curr->next;
}
}
}
void removedulicate(struct node **head)
{
if (NULL ==(*head) )
{
printf("No node,failed to delete\n");
return;
}
struct node* current = (*head);
struct node* runner=NULL;;
while (current)
{
runner = current;
while (runner->next)
{
if (current->data == runner->next->data)
{
node* temp = runner->next;
runner->next = runner->next->next;
free(temp);
}
else
{
runner = runner->next;
}
}
current = current->next;
}
}
int main()
{
struct node *head=NULL;
//#if 0
pushAtBegin(&head,1);
pushAtBegin(&head,2);
pushAtBegin(&head,3);
pushAtBegin(&head,4);
pushAtBegin(&head,5);
pushAtBegin(&head,6);
pushAtBegin(&head,7);
pushAtBegin(&head,8);
pushAtBegin(&head,9);
//#endif
#if 0
pushAtEnd(&head,1);
pushAtEnd(&head,2);
pushAtEnd(&head,3);
pushAtEnd(&head,4);
pushAtEnd(&head,5);
pushAtEnd(&head,6);
pushAtEnd(&head,7);
pushAtEnd(&head,8);
pushAtEnd(&head,9);
#endif
printfList(head);
removedulicate(&head);
deleteNode(&head,9);
printfList(head);
deleteNode(&head,4);
printfList(head);
getchar();
return 0;
} |
H**********5
发帖数: 2012 | 27 贴下自己的代码，完整版，
绝对没问题，可以跑。 |
h*********r
发帖数: 76 | 28 请问层主能否解释一下？
C语言学的不好- -
多谢！
【在 z***b 的大作中提到】
: 楼主这个程序签名就不对.应该为
: void deleteNode(struct node **head, int data);
: 或者
: struct node *deleteNode(struct node *head, int data)；
|
x*******9
发帖数: 138 | 29 这题确实微坑。
何况函数原型都是错的。
建议还是想明白再开始写吧。每次一碰到见过的题，心里一激动，总会手抖一下。
Design -> Proof of Correctness -> Analysis -> Implement
这四步真是一步不能少啊。 |
p***y
发帖数: 637 | 30 这个head大概是个dummy head node吧
【在 z***b 的大作中提到】
: 你觉得烙印这个声明是对的？
: http://geeksquiz.com/linked-list-set-3-deleting-node/
: 看看这个链接，可以想想烙印那个声明为啥不好。
|
|
|
H**********5
发帖数: 2012 | 31 C语言传参机制是拷贝的，都放在堆栈里，函数返回后传递的值是不会改变的。
如果你想改变传递的参数，必须传递其地址给一个指针，
但如果你想改变某个指针，那就传递指向该指针的指针。
那就只有2种方法，
（1）在函数中返回一个指针，将返回值给这个指针
（2）传递一个2级指针，即**.
这两种方法对应那两种原型。
【在 h*********r 的大作中提到】
: 请问层主能否解释一下？
: C语言学的不好- -
: 多谢！
|
H**********5
发帖数: 2012 | 32 之前看前面某童鞋贴的代码里的dummy指针，之前没接触过感觉晕。
下午研究了下，
原来就是复制个节点的技巧，因为单链表删除某节点必须先找到欲删除节点的前面一个
节点，但如果要删除头节点，没有前面的节点如何处理，于是生成一个dummy点，将
dummy的next指向头节点，然后删除头节点，最后返回dummy的next，间接的更新头节点，
但这种只适合函数原型为让你返回指针的形式，即 strcut node* xxx(struct node *
root)
如果烙印让你为void形式，入参为**形式直接更新头节点的话，
那就只能老老实实
void xx(struct node **root)了。 |
h*********r
发帖数: 76 | 33 那就是说如果是原来那种传递1级指针的原型
如果想要删除的结点是head的话，就会出现问题？函数返回后，head还是原来的head？
然后想要删除的结点是除了head之外的结点话，传递1级指针的那个原型也是能够正常
删除的，对吗？
多谢！
【在 H**********5 的大作中提到】
: C语言传参机制是拷贝的，都放在堆栈里，函数返回后传递的值是不会改变的。
: 如果你想改变传递的参数，必须传递其地址给一个指针，
: 但如果你想改变某个指针，那就传递指向该指针的指针。
: 那就只有2种方法，
: （1）在函数中返回一个指针，将返回值给这个指针
: （2）传递一个2级指针，即**.
: 这两种方法对应那两种原型。
|
s***h
发帖数: 662 | 34
在你的程序里，你并没有改变head吧？难道它不是一直指向那个节点么？所以这样的原
型和你的实现也算ok
【在 H**********5 的大作中提到】
: C语言传参机制是拷贝的，都放在堆栈里，函数返回后传递的值是不会改变的。
: 如果你想改变传递的参数，必须传递其地址给一个指针，
: 但如果你想改变某个指针，那就传递指向该指针的指针。
: 那就只有2种方法，
: （1）在函数中返回一个指针，将返回值给这个指针
: （2）传递一个2级指针，即**.
: 这两种方法对应那两种原型。
|
z***y
发帖数: 73 | 35 不得不说楼主其实挺有创造力的，ls有几个哥们没仔细看代码吧。
形参给的是指针，而不是指针的指针，楼主为了处理删除首节点，苦心写了第一段代码
，把次节点数据拷贝到首节点，然后删除次节点。蛮有想法：）
估计是函数原型给错了，哈哈哈哈。 |
