/**
* 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;
}
-
I don't see any problems with this codebake– bake2019-04-04 04:56:20 +00:00Commented Apr 4, 2019 at 4:56
-
2What error do you get?user2313067– user23130672019-04-04 04:57:10 +00:00Commented Apr 4, 2019 at 4:57
-
can you povide a full compilable piece of code hat causes the problem?OznOg– OznOg2019-04-04 04:59:23 +00:00Commented Apr 4, 2019 at 4:59
-
no I did not get a problem but leetcode compiler says you used a memory which has been freed, but I don't thinks so. It may be a problem on their partbake– bake2019-04-04 05:07:02 +00:00Commented Apr 4, 2019 at 5:07
-
@bake To make sense of that, we'd need enough code to replicate the problem.David Schwartz– David Schwartz2019-04-04 05:17:22 +00:00Commented Apr 4, 2019 at 5:17
|
Show 2 more comments
1 Answer
This code works on Xcode but fails in leetcode compiler
Well, the code is not working on any platform.
The test you have done on Xcode must have been incomplete as the code has undefined behavior on any platform.
Look at this simple example:
#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;
}
Example output:
0x558311c02260 1->0x558311c02280 42->0x558311c022a0 1
Free val 0x558311c02280 42
0x558311c02260 1->0x558311c02280 42
As you can see there are two problems:
The resulting list is 1->42 but we expected 1->1 In other words - the list is broken.
The node printed in the last line is the node that we have just freed (i.e. 0x558311c02280). That is undefined behavior.
The problem is this line:
beforeNode = p->next;
it shall be
beforeNode->next = p->next;
Output after above change:
0x561def3e6260 1->0x561def3e6280 42->0x561def3e62a0 1
Free val 0x561def3e6280 42
0x561def3e6260 1->0x561def3e62a0 1
Now the list is correct and there is no use of freed memory.
Comments
