/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode *beforeNode = head;
while(beforeNode != NULL){
if(head == beforeNode && head->val == val){
struct ListNode* q = head;
head = q->next;
beforeNode = head;
free(q);
}
else if(beforeNode->next != NULL && beforeNode->next->val == val){
struct ListNode *p = beforeNode->next;
beforeNode = p->next;
free(p);
}
else
beforeNode = beforeNode->next;
}
return head;
}
最佳答案
This code works on Xcode but fails in leetcode compiler
好吧,该代码在任何平台上都无法运行。
您在 Xcode 上完成的测试一定是不完整的,因为代码在任何平台上都有未定义的行为。
看这个简单的例子:
#include <stdio.h>
#include <stdlib.h>
struct ListNode
{
struct ListNode *next;
int val;
};
void printList(struct ListNode* p)
{
if (p)
{
printf("%p %d", (void*)p, p->val);
while(p->next)
{
printf("->");
p = p->next;
printf("%p %d", (void*)p, p->val);
}
}
printf("\n");
}
// Function from question
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode *beforeNode = head;
while(beforeNode != NULL){
if(head == beforeNode && head->val == val){
struct ListNode* q = head;
head = q->next;
beforeNode = head;
free(q);
}
else if(beforeNode->next != NULL && beforeNode->next->val == val){
struct ListNode *p = beforeNode->next;
beforeNode = p->next;
printf("Free val %p %d\n", (void*)p, p->val);
free(p);
}
else
beforeNode = beforeNode->next;
}
return head;
}
int main()
{
// Initialize a list with three element like: 1->42->1->NULL
struct ListNode *head = malloc(sizeof *head);
head->val = 1;
head->next = malloc(sizeof *head);
head->next->val = 42;
head->next->next = malloc(sizeof *head);
head->next->next->val = 1;
head->next->next->next = NULL;
printList(head);
removeElements(head, 42);
printList(head);
return 0;
}
示例输出:
0x558311c02260 1->0x558311c02280 42->0x558311c022a0 1
Free val 0x558311c02280 42
0x558311c02260 1->0x558311c02280 42
如您所见,存在两个问题:
结果列表是 1->42,但我们预期是 1->1 换句话说 - 列表已损坏。
最后一行打印的节点是我们刚刚释放的节点(即0x558311c02280)。这是未定义的行为。
问题出在这一行:
beforeNode = p->next;
应该是
beforeNode->next = p->next;
上述更改后的输出:
0x561def3e6260 1->0x561def3e6280 42->0x561def3e62a0 1
Free val 0x561def3e6280 42
0x561def3e6260 1->0x561def3e62a0 1
现在列表是正确的,并且没有使用已释放的内存。
关于c - 此代码在 Xcode 上可以运行,但在 leetcode 编译器中失败,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55508129/