当前位置：首页 > article >正文

【Leetcode】203.移除链表元素

article 2025/3/19 15:30:11

一、题目

在这里插入图片描述

二、思路

2.1 解题思路

应对第一个示例，就是遇到不同就跳过，遇到相同就删除。如果直接删除当前节点的话，就找不到前面一个节点，无法前一个节点next到当前的下一个节点。所以引入了一个pre来存储前一个节点。
第二个示例和第三个示例，因为可能上来就遇到空链表或者是全是相同于所给值的链表，那就需要对头指针进行判断了，先来一个while循环遍历到合适的头指针位置，不相同才开始执行第一套流程

2.2 代码尝试

/**
 * 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) {
        while(head){
            if(head->val==val){
                head=head->next;
            }else{
                break;
            }
             
        }

        // 创建一个哑节点，指向头指针
        ListNode* dummy=new ListNode(0);
        dummy->next=head;

        ListNode* p=head;
        ListNode* pre=dummy;
        while(p){
            if(p->val==val){
                p=p->next;
                pre->next=p;
                
            }else{
                pre=p;
                p=p->next;
            }
        }
        return head;
    }
};

在这里插入图片描述

2.3 疑难问题

2.4 AI复盘

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 创建一个哑节点，指向头指针
        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* pre = dummy;
        while (pre->next) {
            if (pre->next->val == val) {
                ListNode* temp = pre->next;
                pre->next = pre->next->next;
                delete temp; // 释放内存，避免内存泄漏
            } else {
                pre = pre->next;
            }
        }

        ListNode* newHead = dummy->next;
        delete dummy; // 释放哑节点的内存
        return newHead;
    }
};

原来的代码中，head 的处理和后续节点的处理是分开的，优化后的代码通过哑节点统一处理，减少了冗余代码。
从哑节点开始，每次判断哑节点的下一个节点是否与Val相同，这样就省去了原来代码第一个判断Head。

三、解法

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) {
            return head;
        }
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/remove-linked-list-elements/solutions/813358/yi-chu-lian-biao-yuan-su-by-leetcode-sol-654m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。