【刷题】203. 移除链表元素

---

203. 移除链表元素

一、题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点

二、示例

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

输入：head = [], val = 1
输出：[]

三、实现

方法1-找到前一个节点修改next指向

找到值为val的前一个节点，然后链接到val的后一个节点，再把val删除

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* prev = NULL, * cur = head;while (cur) {if (cur->val == val) {if (prev) {// 2.cur->val为valprev->next = cur->next;free(cur);cur = prev->next;}else {// 0.删除val开头的链表cur = head->next;free(head);head = cur;}}else {// 1.遍历链表，直到cur为空，或者cur->val为valprev = cur;cur = cur->next;}}return head;
}

方法2-不是val的尾插重构

遍历当前链表，把不是val的节点拿下来尾插。

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur = head;struct ListNode* newhead = NULL, * tail = NULL;while (cur) {if (cur->val != val) {// 1.不为val的节点以尾插PushBack的方式重新构建链表if (!tail) {// 1.1尾插第一个元素newhead = tail = cur; }else {// 1.2尾插tail->next = cur;tail = tail->next;}cur = cur->next;}else {// 2.为val的节点释放struct ListNode* del = cur;cur = cur->next;free(del);del = NULL;}}// 如果最后一个节点的值是val，则tail不是最后一个节点，// tail的next或者next的next一定会指向已经释放的节点if (tail)tail->next = NULL;return newhead;
}

---

总结

再次回顾单链表实现时，尾插的细节分析，注意尾插时需要考虑链表为空的情况。