LeetCode - 203. 移除链表元素

目录

题目

解题思路

读者可能出现的错误写法

正确的写法

---

题目

203. 移除链表元素 - 力扣（LeetCode）

解题思路

使用哨兵节点：

• 创建一个哨兵节点(dummy)，将其next指向原链表头节点

• 哨兵节点的作用是统一处理所有情况，特别是当头节点需要被删除时

双指针遍历：

• 使用两个指针：prev(前一个节点)和cur(当前节点)

• prev初始指向哨兵节点，cur初始指向头节点

删除匹配节点：

• 遍历链表，当发现cur节点的值等于目标值时：

• 将prev的next指向cur的next，跳过cur节点

• 释放cur节点内存

• 更新cur为prev的next

• 如果cur节点值不等于目标值：

• prev和cur都向前移动一步

返回新头节点：

• 新的头节点是哨兵节点的next

• 释放哨兵节点

• 返回新头节点

时间和空间复杂度

• 时间复杂度：O(n)，需要遍历整个链表一次

• 空间复杂度：O(1)，只使用了常数额外空间

关键点

• 使用哨兵节点简化了头节点可能被删除的情况处理

• 正确处理指针移动，特别是在删除节点后的指针更新

• 注意内存管理，删除节点时释放内存

读者可能出现的错误写法

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy = new ListNode(0);dummy ->next = head;ListNode* prev = dummy;ListNode* cur = head;while(cur!=nullptr){if(cur==val){prev->next = cur->next;}prev = cur;cur = cur->next;}ListNode* newhead = dummy->next;delete dummy;return newhead;}
};

if(cur==val) 这里你是在比较指针cur和整数val，这是错误的。应该比较节点的值：if(cur->val==val) 

在删除节点后，指针移动逻辑也有问题。当找到要删除的节点时，你应该更新cur但不更新prev。

正确的写法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy = new ListNode(0);dummy ->next = head;ListNode* prev = dummy;ListNode* cur = head;while(cur!=nullptr){if(cur->val==val){prev->next = cur->next;delete cur;cur = prev->next;}else{prev = cur;cur = cur->next;}}ListNode* newhead = dummy->next;delete dummy;return newhead;}
};