跳转至

203 移除链表元素

leetcode

移除链表元素本质上步骤为:

  1. 找到待移除元素curNode的前驱节点prevNode和后继节点nextNode(curNode->next)
  2. prevNode->next = curNode->next
  3. 释放内存delete curNode

有两种做法:原链表操作和引入哑节点

  • 原链表操作意味着需要分两步操作

    1. 因为头部节点没有前驱节点,因此需要额外处理。处理方法很简单:

      ListNode* tmp = head;
      head = head->next
      delete tmp;
      
    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) {
        if(!head)
            return head;
        while(head && head->val == val){
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        //到这一步,head有两种可能,nullptr 或者 head->val != val
        ListNode* cur = head;
        // cur可能为nullptr,因此需要判断cur是否为nullptr再取cur->next
        // cur->next可能为空,所以需要判断cur->next是否为nullptr再取cur->next->val
        while(cur && cur->next){
            if(cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else
                cur = cur->next;
        }

        return head;
    }
};

引入哑节点

/**
 * 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* dummyNode = new ListNode(-1,head);
        ListNode* cur = dummyNode;
        // 边界条件:判断要删除的节点是否为空
        while(cur->next != nullptr){
            if(cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = tmp->next;
                delete tmp;
            }
            // 这里要注意:一定要用else
            // 因为删了节点之后,cur->next改变了,需要先判断cur->next是否为空再取cur->next->val
            else
                cur = cur->next;
        }
        head = dummyNode->next;
        delete dummyNode;
        return head;
    }
};