当前位置: 首页 > news >正文

刷题 - 数据结构(二)链表

1. 链表

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里面放的就是第一个节点的地址,
}
  1. 依据数组创建列表的时候,需要考虑到:函数内部不好获得数组的长度。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);
}
  1. 总结:其实就是:确定指向(pre->next = ),激活当前(pre = pre->next)
  2. 总代码:
 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 个结点

开始的想法:

  1. 必须获得链表长度;(后面发现不一定)
  2. 循环到某个的时候跳过就好
    但是发现还少了一些
  3. 必须要用哑结点(头节点要一视同仁);

下面是我的代码,没用到哑结点,要不断排除特殊情况。

    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 题目&#xff1a;合并两个有序链表 链表的建立与插入&#xff1a;关键在于留出头部&#xff0c;创建迭代指针。 ListNode* head new ListNode; // 通过new 创建了一个数据类型为ListNode的数据 并把该数据的地址赋值给ListNodeListNode* p 0; // 再创建一个数据…...

用于隔离PWM的光耦合器选择和使用

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

面试完阿里,字节,腾讯的测试岗,复盘以及面试总结

前段时间由于某些原因辞职了&#xff0c;最近一直在面试。面试这段时间&#xff0c;经历过不同业务类型的公司&#xff08;电商、酒店出行、金融、新能源、银行&#xff09;&#xff0c;也遇到了很多不同类型的面试官。 参加完三家大厂的面试聊聊我对面试的一些看法&#xff0…...

分享一个外贸客户案例

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

【Kubernetes】第二篇 - 购买阿里云 ECS 实例

一&#xff0c;前言 上一篇&#xff0c;简单介绍了 CI/CD 的概念以及 ECS 服务规划&#xff0c;搭建整套服务需要三台服务器&#xff0c;配置如下&#xff1a; ECS 配置启动服务说明2核4GJenkins Nexus Dockerci-server2核4GDocker Kubernetesk8s-master1核1GDocker Kube…...

数影周报:据传国内45亿条快递数据泄露,聆心智能完成Pre-A轮融资

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

Leetcode力扣秋招刷题路-0073

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

遥感数字图像处理

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

深度学习常用的python函数(一)

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

2023年美国大学生数学建模A题:受干旱影响的植物群落建模详解+模型代码(一)

目录 前言 一、题目理解 背景 解析&#xff1a; 要求 二、建模 1.相关性分析 2.相关特征权重 只希望各位以后遇到建模比赛可以艾特认识一下我&#xff0c;我可以提供免费的思路和部分源码&#xff0c;以后的数模比赛只要我还有时间肯定会第一时间写出免费开源思路&…...

PPS文件如何转换成PPT?附两种方法

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

ParallelsDesktop安装【亲测可行】

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

在 Python 中只接受数字作为用户输入

只接受数字作为用户输入&#xff1a; 使用 while True 循环进行循环&#xff0c;直到用户输入一个数字。使用 float() 类尝试将值转换为浮点数。如果用户输入了一个数字&#xff0c;请使用 break 语句跳出循环。 while True:try:# &#x1f447;️ 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问题产生原因&#xff1a;因机房意外掉电导致集群部分机器两次掉电导致Elasticsearch重启&#xff0c;Elasticsearch重启后看似正常但某些index无数据。经排查判断为Elasticsearch的部分ind…...

Spring入门案例三:注解进行引用类型的自动装配

本系列文章将会带领大家进行Spring的全面学习&#xff0c;持续关注我&#xff0c;不断更新中… 一.案例分级 简单解析:配置类替代以前的配置文件&#xff0c;实体类提供对象&#xff0c;业务类中有实体类的引用对象&#xff0c;在业务层中实现引用类的自动装配。 二.各层代码…...

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 使用方法部署文档…...

软件测试项目实战(附全套实战项目教程+视频+源码)

开通博客以来&#xff0c;我更新了很多实战项目&#xff0c;但一部分小伙伴在搭建环境时遇到了问题。 于是&#xff0c;我收集了一波高频问题&#xff0c;汇成本篇&#xff0c;供大家参考&#xff0c;避免重复踩坑。 如果你还遇到过其他坑和未解决的问题&#xff0c;可在评论区…...

Python seek()和tell()函数详解

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

数据库系统:1. 绪论

更好的阅读体验\huge{\color{red}{更好的阅读体验}}更好的阅读体验 文章目录1.1 数据库系统概述1.1.1 基本概念数据&#xff08;data&#xff09;数据库&#xff08;DataBase, DB&#xff09;数据库管理系统&#xff08;DataBase Management System, DBMS&#xff09;数据库系统…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

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

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Java设计模式:责任链模式

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

【QT控件】显示类控件

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