【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点(下)

简介: 【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点

2、AB10 ~ AB11题解

题目链接:合并两个排序链表

faa10bfc16b14850b96052cbbb997e94.png



2.1、解题思路

新创建一个链表,根据已知的两个递增链表的元素大小来升序的在新链表中存储数据

头插法建表,使用另外的链表指针作为辅助

当两个已知链表有一个已经遍历完时,直接让辅助指针指向非空的链表结点即可

2.2、代码实现及注释

本题源码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* vhead = new ListNode(-1);
        ListNode* cur = vhead;
        while (pHead1 && pHead2) {
            if (pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        cur->next = pHead1 ? pHead1 : pHead2;
        return vhead->next;
    }
};

重要注释:


new ListNode(-1) 相当于创建了一个头结点,cur作为头插的赋值指针

while循环内部为头插法建立升序链表的过程

三目运算符目的是让新链表的尾指向剩余链表的头

最后返回的时候不需要头结点,因此结果为vhead->next

反转链表解析的博文地址:反转链表及进阶


反转链表的题目中我用了vector容器自带的reverse方法,非常适合入门新手


3、AB12 删除链表的节点

题目链接:删除链表节点

8681a509631e4b3fb936c29047578153.png



3.1、解题思路

观察链表的定义代码可知,该题链表是没有头结点的,那么就可以分情况讨论:


若链表第一个结点的值为目标值,直接返回结点的下一个指向即可

若链表首结点不是目标值,将其当作头结点即可,使用两个移动指针的方法:

步骤与本文上面 模板链表 步骤几乎一致,不做赘述

3.2、代码实现

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param val int整型
     * @return ListNode类
     */
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* ptr = head->next;
        if(head->val==val) return ptr;
        ListNode* pre = head;
        while (ptr) {
            if (ptr->val == val) {
                if (ptr->next) {
                    pre->next = ptr->next;
                    break;
                } else {
                    pre->next = NULL;
                }
            } else {
                pre = ptr;
                ptr = ptr->next;
            }
        }
        return head;
    }
};

链表题打牢基础的话,对后续数据结构的理解也有很大帮助,建议大家多多练习,题目旁的链接点进去即可挑战!


目录
相关文章
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
18天前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
18天前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)
|
18天前
|
算法 索引
经典算法之链表篇
经典算法之链表篇
|
15天前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
28 0
|
19天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
28 0
|
7天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
26天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
4天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。