Leetcode中删除链表中等于val的节点，如何实现？

本文共计876个文字，预计阅读时间需要4分钟。

链表删除节点+方法一：+使用前后两个指针，cur指向当前节点，prev指向前一个节点，通过改变指针和释放节点来删除val+初步代码+，+问题：+/*+Definition for singly-linked list.+*+/+struct+ListNode+%7B+/*+int+val;+*+/+ListNode*+next;+*+/+ListNode(int x) : val(x), next(NULL) {}+*+/+

力扣链接

方法一:

使用前后两个指针,cur指向当前位置,prev指向前一个位置,通过改变指向和释放结点来删除val

初步代码,还存在问题:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev = NULL; struct ListNode* cur = head; while(cur) { if(cur->val != val) { prev = cur; cur = cur->next; } else { prev->next = cur->next; free(cur); // cur = cur->next;//错误,cur已经被释放,野指针 cur = prev->next; } } return head; }

null pointer出现了空指针

通过测试用例代码走读分析问题:

如果第一个就是要删的值,也就是头删,会出现问题

所以这种情况要单独处理

最终代码:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev = NULL; struct ListNode* cur = head; while(cur) { if(cur->val != val) { prev = cur; cur = cur->next; } else { if(prev == NULL) { head = cur->next; free(cur); cur = head; } else { prev->next = cur->next; free(cur); //cur = cur->next;//和下一句等价,但是cur已经释放,这句会出现野指针 cur = prev->next; } } } return head;//返回一个新的头,不需要用二级指针 }

---

方法二:

把不是val的值尾插到新链表

初步代码:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newHead= NULL,* tail = NULL; struct ListNode* cur = head; while(cur) { if(cur->val != val) { //尾插 if(tail == NULL) { newHead = tail = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; } else { struct ListNode* next = cur->next; free(cur); cur = next; } } return newHead; }

通过走读代码我们发现,当最后一个结点的值为val时,释放节点后前面尾插的结点仍然指向最后一个结点,这里只需要将tail->next置空即可,修改后代码如下:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newHead= NULL,* tail = NULL; struct ListNode* cur = head; while(cur) { if(cur->val != val) { //尾插 if(tail == NULL) { newHead = tail = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; } else { struct ListNode* next = cur->next; free(cur); cur = next; } } tail->next = NULL; return newHead; }

但是代码仍然存在错误,运行如下:

显而易见,需要考虑链表为空的情况

改进后代码:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { if(head== NULL) { return NULL; } struct ListNode* newHead= NULL,* tail = NULL; struct ListNode* cur = head; while(cur) { if(cur->val != val) { //尾插 if(tail == NULL) { newHead = tail = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; } else { struct ListNode* next = cur->next; free(cur); cur = next; } } tail->next = NULL; return newHead; }

报错:

这时代码直接指向最后一个else,此时tail为空,tail->next不合理,所以干脆前面不进行判断,而在后面对tail进行判断

最终代码如下:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* newHead= NULL,* tail = NULL; struct ListNode* cur = head; while(cur) { if(cur->val != val) { //尾插 if(tail == NULL) { newHead = tail = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; } else { struct ListNode* next = cur->next; free(cur); cur = next; } } if(tail) { tail->next = NULL; } return newHead; }