leetcode——203.移除链表元素

🐨1.题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

🪅2.解法1-头节点迭代

🌿2.1 思路

我们可以定义两个指针，一个指针cur指向头节点，遍历链表，遇到相同的值讲节点删除，但是如果将节点直接释放，则会找不到下次需要指向的位置；所以还需用另一个指针prev记录当前节点的前一个位置，便于修改next指针。

注意事项：

1. 在删除头节点时，要更新头节点指针head，防止链表丢失。
2. 删除节点时，需先保存该节点的next，防止野指针。

🌿2.2 代码实现

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;cur = cur->next;}else{prev->next = cur->next;free(cur);cur = prev->next;}}}return head;
}

🦆3. 解法2-创建新链表

🎏3.1 思路

我们可以创建一个新的链表，将不等于val的值尾插到新链表，最后返回新链表的头节点位置。

注意事项：

1. 需要考虑新链表为空（全部都是需要删除的值）和链表为空的情况
2. 如果最后一个值为要删除的值，则需要手动讲尾节点的next置空。

🎏3.2 代码实现

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;
}

🐐4. 题目链接

leetcode–203.移除链表元素