刷题 - 数据结构(二)链表
1. 链表
1.1 题目:合并两个有序链表
- 链表的建立与插入:关键在于留出头部,创建迭代指针。
ListNode* head = new ListNode; // 通过new 创建了一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodeListNode* p = 0; // 再创建一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodep = head; // 把head 里面的地址赋值给p
完整的代码
作者:小陈写不完代码
链接:https://zhuanlan.zhihu.com/p/365219765
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。#include<iostream>
#include<string>
using namespace std;
struct node
{string name;int score;node* next;
};
node* creatList(); // 创建了一个返回值为指向数据类型为node的执政,即返回的是一个地址
int main()
{node* head=creatList();
}
node* creatList()
{node* head = new node; // 通过new 创建了一个数据类型为node的数据 并把该数据的地址赋值给nodenode* p= new node; // 再创建一个数据类型为node的数据 并把该数据的地址赋值给nodep=head; // 把head 里面的地址赋值给pp->next=NULL; //这里把p指向的数据类型为node的数据里的 指针next指向了空.指针必须有对象 即指向一个地方,你不告诉它 它就乱跑 所以一般都是让它空着while (true) // 这里我选择while循环 因为里面是true 所以会一直进行 ,我们在里面使用条件判断加break跳出来{cout<<"Please enter student name: ";cin>>p->name; // 录入学生的姓名cout<<"Please enter student score: ";cin>>p->score; // 输入学生的分数if(p->score <0){break; // 如果分数小于0 跳出循环即输入结束.}node*q =new node; // 没有跳出循环 即继续输入,这时我们再创建一个这些数据类型为node的数据 并把它的地址赋值给 指针变量 q .p->next=q; // 刚刚p指针指向的数据类型为node的数据里的 指针next 指向 q ,节点p 和 节点q连起来了..q->next=NULL; // 指针q指向的数据类型为node的数据里的指针 next 指针也不能乱指,所以我们让它指向 NULLp=q; // 这里我当初就搞了很长时间.还记的嘛 p 和 q 是什么 ,它们两都是指针变量.它们里面放的是地址,而且它们里面的地址是可以给其它的指向相同数据类型的指针的,这里我们把q里面的地址 给了p 这样p里面存放的地址就是这个链表的最后一个节点的地址.如此反复我们就实现了动态输入.}return head; // 这就是为什么我们要设置head了,因为p的地址是不断变化的,而head里面的地址是不变的.而且head里面放的就是第一个节点的地址,
}
- 依据数组创建列表的时候,需要考虑到:函数内部不好获得数组的长度。sizeof 的方法卸载main中可以,但是对于函数的形参指针就不行了。
解决方法:类模板+引用。
template<class T>
void arr(T &a)
{int n = sizeof(a) / sizeof(a[0]);cout << n << endl;
}int main()
{int a[] = { 6,-1,3,-4,-6,9,2,-2,5 };arr(a);
}
- 总结:其实就是:确定指向(pre->next = ),激活当前(pre = pre->next)
- 总代码:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* dummy = new ListNode(0); 记录一下头的位置ListNode* cur = dummy; 弄个哨兵变量用于遍历while (l1 != nullptr && l2 != nullptr) {ListNode** pp = (l1->val < l2->val) ? &l1 : &l2;cur->next = *pp;cur = cur->next;*pp = (*pp)->next;}cur->next = (l1 == nullptr) ? l2 : l1;ListNode* ans = dummy->next;delete dummy;return ans;}
2. 删除排序链表中的重复元素
// 原来的代码有错误
ListNode* deleteDuplicates(ListNode* head) { ListNode* new_head = new ListNode(head->val);ListNode* h = new_head;int temp = head->val;head = head->next;while (head != nullptr) {if (head->val != temp) {h->next = head;h = h->next;}temp = head->val;head = head->next;}return new_head;
}
修改了
ListNode* deleteDuplicates(ListNode* head) {if (!head) {return head;}ListNode* new_head = new ListNode(head->val);ListNode* h = new_head;int temp = head->val;head = head->next;while (head != nullptr) {if (head->val != temp) {h->next = head;h = h->next;temp = head->val;head = head->next;}else {temp = head->val;head = head->next;h->next = head; // 这句话一定要,他不是定义,他是修改!!!}}return new_head;
}
题目四、 删除链表的倒数第 N 个结点
开始的想法:
- 必须获得链表长度;(后面发现不一定)
- 循环到某个的时候跳过就好
但是发现还少了一些 - 必须要用哑结点(头节点要一视同仁);
下面是我的代码,没用到哑结点,要不断排除特殊情况。
ListNode* removeNthFromEnd(ListNode* head, int n) {int n1 = 0;ListNode* cur = head;while (cur != nullptr) {++n1;cur = cur->next;}if (n1 ==1) return head->next; // 啰嗦了,但是必要的int k = 0;cur = head;if (k > n1 - n -1) return head->next;while (k < n1 - n -1) {++k;cur = cur->next;}cur->next = cur->next->next;return head;}
把上面的代码稍微修改,加入哑结点就好。
class Solution {
public:int getLength(ListNode* head) {int length = 0;while (head) {++length;head = head->next;}return length;}ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);int length = getLength(head);ListNode* cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur->next;}cur->next = cur->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};作者:LeetCode-Solution
链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
当然,双指针发可以避免获取总长度
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);ListNode* first = head;ListNode* second = dummy;for (int i = 0; i < n; ++i) {first = first->next;}while (first) {first = first->next;second = second->next;}second->next = second->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};作者:LeetCode-Solution
链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章:
刷题 - 数据结构(二)链表
1. 链表 1.1 题目:合并两个有序链表 链表的建立与插入:关键在于留出头部,创建迭代指针。 ListNode* head new ListNode; // 通过new 创建了一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodeListNode* p 0; // 再创建一个数据…...

用于隔离PWM的光耦合器选择和使用
光耦合器(或光隔离器)是一种将电路电隔离的器件,不仅在隔离方面非常出色,而且允许您连接到具有不同接地层或在不同电压电平下工作的电路。光耦合器具有“故障安全”功能,因为如果受到高于最大额定值的电压,…...

面试完阿里,字节,腾讯的测试岗,复盘以及面试总结
前段时间由于某些原因辞职了,最近一直在面试。面试这段时间,经历过不同业务类型的公司(电商、酒店出行、金融、新能源、银行),也遇到了很多不同类型的面试官。 参加完三家大厂的面试聊聊我对面试的一些看法࿰…...

分享一个外贸客户案例
春节期间一个外贸人收到了客户的回复,但因为自己的处理方式造成了一个又一个问题,我们可以从中学到一些技巧和知识。“上次意大利的客人询价后,一直没回复(中间有打过电话,对方说口语不行,我写过邮件跟进过…...

【Kubernetes】第二篇 - 购买阿里云 ECS 实例
一,前言 上一篇,简单介绍了 CI/CD 的概念以及 ECS 服务规划,搭建整套服务需要三台服务器,配置如下: ECS 配置启动服务说明2核4GJenkins Nexus Dockerci-server2核4GDocker Kubernetesk8s-master1核1GDocker Kube…...

数影周报:据传国内45亿条快递数据泄露,聆心智能完成Pre-A轮融资
本周看点:据传国内45亿条快递数据泄露;消息称微软解雇150 名云服务销售;消息称TikTok计划在欧洲再开两个数据中心;衣服长时间放购物车被淘宝客服嘲讽;聆心智能完成Pre-A轮融资......数据安全那些事据传国内45亿条快递数…...

Leetcode力扣秋招刷题路-0073
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 73. 矩阵置零 给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 1: 输入:mat…...

遥感数字图像处理
遥感数字图像处理 来源:慕课北京师范大学朱文泉老师的课程 遥感应用:遥感制图、信息提取 短期内了解知识结构–>有选择的剖析经典算法原理–>系统化知识结构、并尝试实践应用 跳出算法(尤其是数学公式) 关注原理及解决问…...

深度学习常用的python函数(一)
由于我只简单的学过python和pytorch,其中有很多函数的操作都还是一知半解的,其中有些函数经常见到,所以就打算记录下来。 1.zip zip(*a):针对单个可迭代对象压缩成n个元组,元组数量n等于min(a中元素的最小长度) a [(1, 2), (3…...

2023年美国大学生数学建模A题:受干旱影响的植物群落建模详解+模型代码(一)
目录 前言 一、题目理解 背景 解析: 要求 二、建模 1.相关性分析 2.相关特征权重 只希望各位以后遇到建模比赛可以艾特认识一下我,我可以提供免费的思路和部分源码,以后的数模比赛只要我还有时间肯定会第一时间写出免费开源思路&…...

PPS文件如何转换成PPT?附两种方法
在工作中,PPS文件的使用还是很广泛的,因为作为幻灯片放映文件,点击后就能直接播放,十分方便。但如果想要修改PPS里的内容,PPS是无法编辑的,我们需要把文件转换成PPT,再进行修改。 那PPS文件如何…...

ParallelsDesktop安装【亲测可行】
我这边安装的是macos最新系统 (Ventura13.2) 本文参考这篇文章安装,但是你完全按照这篇文章会报错,具体可行操作记录如下 一、下载软件和补丁 1、点这里去下载补丁18.0.1 2、点这里去下载对应版本的ParallelsDesktop18.0.1,安装上到试用这里…...

在 Python 中只接受数字作为用户输入
只接受数字作为用户输入: 使用 while True 循环进行循环,直到用户输入一个数字。使用 float() 类尝试将值转换为浮点数。如果用户输入了一个数字,请使用 break 语句跳出循环。 while True:try:# 👇️ use int() instead of floa…...

【集合】JAVA基础篇(二)
目录一、java常用集合1、Java集合接口的作用2、Java集合常用实现类的作用二、Collection 常用的方法三、List 集合接口1、ArrayList类的常用方法2、LinkList类中的方法3、Vector4、ArrayList 类和 LinkedList 类的区别四、Set 集合1、HashSet 类2、TreeSet 类3、HashSet 和 Tre…...
机房意外掉电导致Elasticsearch的部分index无数据的修复过程
环境 :华为大数据集群FusionInsight V100R002C800SPC200、Elasticsearch 6.1.3、Kibana问题产生原因:因机房意外掉电导致集群部分机器两次掉电导致Elasticsearch重启,Elasticsearch重启后看似正常但某些index无数据。经排查判断为Elasticsearch的部分ind…...

Spring入门案例三:注解进行引用类型的自动装配
本系列文章将会带领大家进行Spring的全面学习,持续关注我,不断更新中… 一.案例分级 简单解析:配置类替代以前的配置文件,实体类提供对象,业务类中有实体类的引用对象,在业务层中实现引用类的自动装配。 二.各层代码…...
kubernet + kubevirt + ceph 汇总文档
目的 1 创建 kubenetes 集群 2 kubenetes 集群上部署 kubevirt 3 kubernetes 支持 ceph 存储 4 VMI 可以存储在 ceph rbd 存储中并正常使用 参考部署文档 名称连接备注centos8 + kubernetes 1.24 master/node 节点部署文档kubernetes 集群部署kubectl top node 使用方法部署文档…...

软件测试项目实战(附全套实战项目教程+视频+源码)
开通博客以来,我更新了很多实战项目,但一部分小伙伴在搭建环境时遇到了问题。 于是,我收集了一波高频问题,汇成本篇,供大家参考,避免重复踩坑。 如果你还遇到过其他坑和未解决的问题,可在评论区…...

Python seek()和tell()函数详解
在讲解 seek() 函数和 tell() 函数之前,首先来了解一下什么是文件指针。我们知道,使用 open() 函数打开文件并读取文件中的内容时,总是会从文件的第一个字符(字节)开始读起。那么,有没有办法可以自定指定读…...

数据库系统:1. 绪论
更好的阅读体验\huge{\color{red}{更好的阅读体验}}更好的阅读体验 文章目录1.1 数据库系统概述1.1.1 基本概念数据(data)数据库(DataBase, DB)数据库管理系统(DataBase Management System, DBMS)数据库系统…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Java设计模式:责任链模式
一、什么是责任链模式? 责任链模式(Chain of Responsibility Pattern) 是一种 行为型设计模式,它通过将请求沿着一条处理链传递,直到某个对象处理它为止。这种模式的核心思想是 解耦请求的发送者和接收者,…...

【QT控件】显示类控件
目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏:QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...