关关的刷题日记77 – Leetcode 203.Remove Linked List Elements- 专知

会员服务 ·

关关的刷题日记77 – Leetcode 203.Remove Linked List Elements

关关

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记77 – Leetcode 203.Remove Linked List Elements

题目

Remove all elements from a linked list of integers that have value val.

Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5

题目要求删掉所有和给定值相等的节点。

思路

思路：如果要删掉一个节点的话，那么就令其前一个节点指向其后面的节点。设置pre，cur，rear三个节点，分别代表前一个节点、当前节点和后一个节点。为了处理被删除节点是头节点的情况，我们在头节点前面设置一个虚拟节点dummy。

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

写了一个不设置dummy的版本，重点注意判断head不能等于nullptr

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *pre, *rear, *cur;
        while(head!=nullptr && head->val==val)
        {
            head=head->next;
        }
        if(head==nullptr)
            return head;
        pre=head;
        cur=head->next;
        while(cur!=nullptr)
        {
            rear=cur->next;
            if(cur->val==val)
            {
                pre->next=rear;
                cur=rear;
            }
            else
            {
                pre=cur;
                cur=rear;
            }
        }
        return head;
    }
};