您现在的位置是:首页 >学无止境 >算法刷题营【Day3】:: 链表篇:单链表结点删除思路:一题辨别哨兵结点的优势(删除有奇效):203. 移除链表元素网站首页学无止境

算法刷题营【Day3】:: 链表篇:单链表结点删除思路:一题辨别哨兵结点的优势(删除有奇效):203. 移除链表元素

MortalSoul&Code 2023-06-01 08:00:02
简介算法刷题营【Day3】:: 链表篇:单链表结点删除思路:一题辨别哨兵结点的优势(删除有奇效):203. 移除链表元素

本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识!


目录:
1. 开篇例题:203. 移除链表元素
2. 题解参考

- - 2.1 方法一:原表操作(不含哨兵结点)
- - 2.2 方法二:虚设哨兵结点辅助法
- - 2.3 方法三:递归法

3. 单链表结点删除思路

4. 方法思路点拨:原表操作(不含哨兵结点)

5. 方法思路点拨:虚设哨兵结点辅助法
6. 相关题集


1. 开篇例题:203. 移除链表元素

例题:点击直飞

在这里插入图片描述


2. 题解参考

2.1 方法一:原表操作(不含哨兵结点)

class Solution {
public:
    // 基于原表操作
    ListNode* removeElements(ListNode* head, int val) {
    // 处理原表第一个结点是删除目标的情况
        while(head != NULL && head->val == val){
        // 头部操作只需移动头部标识
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }
        ListNode* cur = head;
	// 处理删除原表中的目标结点
        while( cur && cur->next ){
        // 非头部操作:使用下文图中写的四部曲:双找一接后释放
            if( cur->next->val == val ){
                cur->next = cur->next->next;
            }
            else{
                cur = cur->next;
            }
        }
        return head;
    }
};

2.2 方法二:虚设哨兵结点辅助法

class Solution {
public:
    // 自定义虚设哨兵结点处理
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* ph = new ListNode(0,head);    
        // 虚设哨兵结点,并指向原表首结点
        ListNode* temp = ph;
        while(temp->next){
            if(temp->next->val == val)
                temp->next = temp->next->next;
            else
                temp = temp->next;
        }
        return ph->next;
    }
};

2.3 方法三:递归法

class Solution {
public:
    // 递归算法处理
    ListNode* removeElements(ListNode* head, int val) {
        if(!head) return head;                          // 表空判断
        head->next =removeElements(head->next,val);     // 
        return head->val == val ? head->next : head;    // 
    }
};

3. 单链表结点删除思路

在这里插入图片描述

对于单链表结点的删除操作,结合结点的定义方式

 * 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) {}
 * };

可知:链表中,前驱节点找到后继节点的方式是:通过前驱节点指针域来标识的!
如上图中的 1 -> 2 -> 3 链表中,如果我们想要删除 结点2,实际只需要让 结点1 的指针域指向 结点3 的结点即可(C/C++ 语言中推荐手动释放结点2)。
【核心代码如下:】

// cur 指向结点2,prev 指向结点1
// 删除代码:
prev->next = cur->next;
delete cur; 

由简单的代码可以看出,我们对于链表删除的关键点是:找到被删除目标结点,以及它的前驱结点!!!


4. 方法思路点拨:原表操作(不含哨兵结点)

注意题设:原题中不含哨兵结点,即 head->val 即得第一个结点值:1(如下图)

在这里插入图片描述

结合上图可知:

  1. 如果删除的目标是第一个结点,我们只需要将 head 后移一位,并释放原第一个结点。
  2. 如果删除的目标不是第一个结点,我们需要使用两个指针,一个用于找到删除目标,另一个指向删除目标的前驱节点。
    如:删除结点值为 6 的第一个结点,我们需要用它的前驱结点指向被删除目标的后继结点。

在这里插入图片描述

5. 方法思路点拨:虚设哨兵结点辅助法

注意题设:原题中不含哨兵结点,即 head->val 即得第一个结点值:1(如下图)

哨兵结点:简而言之就是在哨兵结点的第一个结点前设置一个结点,该节点内的数据域数据利用无意义。
特点:显然:ph->next = head; 即哨兵结点的下一个结点是原表的第一个结点。

在这里插入图片描述

回顾哨兵结点的删除操作:

  1. 只要删除目标不是第一个结点:我们的删除操作都是四部曲,关键就在于找到删除目标的前驱结点。

此时,看向含哨兵结点的:

  1. 现在在原表首结点前增加一个结点,不就是实现了表中删除统一化操作:即:不用单独考虑对首结点的处理!!!

6. 相关题集

27. 移除元素【回顾数组/顺序表的元素移除操作】
237. 删除链表中的节点【指定结点删除:区别于本题,指定删除值为指定数据的结点】

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。