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

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

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月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
98 8
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
111 7
|
1月前
|
机器学习/深度学习 算法 Python
机器学习入门:理解并实现K-近邻算法
机器学习入门:理解并实现K-近邻算法
36 0
|
2月前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
41 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
2月前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
2月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
56 0
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
34 0
|
2月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
81 0
|
18天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
4天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。