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

手撕单链表练习

Topic 1:

LeetCode——203. 移除链表元素

203. 移除链表元素 - 力扣(LeetCode)

移除链表中的数字6

操作很简单,我们只需要把2的指向地址修改就好了,原来的指向地址是6现在改为3

这个思路是完全正确的,但是在链表中增加或删除元素是很麻烦的,我们需要判断前后是否为空指针,情况很多。

我们利用这个思路,可以推广另外的做法,把不是6的元素尾插到一个新链表,这样就可以去除所有6

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* removeElements(struct ListNode* head, int val)
{if(head==NULL){return NULL;}struct ListNode* cur =head;//利用另外的变量遍历//哨兵防止空指针struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));newnode->next=NULL;struct ListNode* tail=newnode;//记录下次尾插的作用while(cur){if(cur->val!=val){tail->next=cur;//尾插到哨兵后面tail=tail->next;//尾向后cur=cur->next;//指针向后}else{struct ListNode* tmp=cur->next;//存下一个,我们释放当前位置free(cur);cur=tmp;}}tail->next=NULL;//到尾了head=newnode->next;//去除哨兵free(newnode);return head;}

Topic 2:

LeetCode——876. 链表的中间结点

876. 链表的中间结点 - 力扣(LeetCode)

找中间很简单,但是假如我们要求时间复杂度为O(N)

我们应该怎么去做?小明一次走一步,小华一次走两步,当小华走完全程的时候,小明走的路程刚刚好是全部路程的一半。通过这个例子,我们可以明白,我们可以定义两个指针来进行查找中间的节点。这种方法叫做快慢指针。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast=head;struct ListNode* slow=head;while(fast  && fast->next)//当元素是奇数个时fast->next为NULL;当元素为偶数个fast为NULL是结束标志{fast=fast->next->next;slow=slow->next;}return slow;
}

Topic 3:

链表中倒数第k个结点

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

链表的倒数第k个元素

我们先处理极端情况:链表为空的时候;k大于链表元素个数

把极端情况处理完,我们思考,当时间复杂度为O(N)时,我们应该怎么样得到倒数第k的节点。倒数第k个就是正数的第n-k个,我们定义两个指针,一个先走k步,然后两个指针同时走,当先走k步的指针到结尾的时候,我们第二个指针就是走到了n-k的位置。

/*** struct ListNode {*    int val;*    struct ListNode *next;* };*//*** * @param pListHead ListNode类 * @param k int整型 * @return ListNode类*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{struct ListNode* fast=pListHead;struct ListNode* slow=pListHead;if(pListHead==NULL){return NULL;}while(k--)//先走k步{if(fast==NULL)//链表的元素小于k{return NULL;}fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow;}

Topic 4:

链表分割

我们先解读题目,给一个链表,给定一个值x,大于x的放后面,小于x的放前面。不改变原来的数据顺序即,原来小于x的值是,4 2 1,我们不改变想对位置 4 2 1.

题目理解清楚了,我们怎么做呢,我们创建两个链表,一个存小于x的值,一个存大于等于x的值,然后连接起来,这样他们的相对位置就没有改变。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x){struct ListNode* gguard;//存大于等于x的数据得哨兵struct ListNode* lguard;//存小于x的哨兵struct ListNode* gtail;//存大于x的尾struct ListNode* ltail;//存小于x的尾struct ListNode* cur=pHead;gguard=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));//申请哨兵lguard=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));//申请哨兵gtail->next=ltail->next=NULL;//哨兵后面一个置空while(cur){if(cur->val>=x){gtail->next=cur;//哨兵后面接插入的链表gtail=gtail->next;//尾向后移}else{ltail->next=cur;ltail=ltail->next;}cur=cur->next;}ltail->next=gguard->next;//连接两个链表gtail->next=NULL;//新链表的最后要置空pHead=lguard->next;free(lguard);free(gguard);return pHead;}
};

Topic 5:

反转链表

206. 反转链表 - 力扣(LeetCode)

反转链表,我们可以利用头插的思路,即我们建立一个新的链表,把一个一个元素头插到第一个,最后插入的元素就是新的头,第一个插入的元素就是新的尾。头插最最要的是更新新的头,新的头就是新插入的元素的地址。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL){return NULL;    }struct ListNode* cur=head;struct ListNode* newnode=NULL;while(cur){struct ListNode* next=cur->next;//存下一个,防止找不到cur->next=newnode;//将链表第一个元素指向newnode指针,下面依次指向newnode=cur;//更新newnode,让newnode一直指向链表的开头cur=next;//链表向后移}return newnode;}

Topic 6:

链表的回文结构

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

链表的回文,怎么判断。我们最直接的方法是,找到中间节点,反转中间节点,得到翻转的链表,与前半段链表比较。如果前半段链表与,后半段链表翻转后的元素都相等,说明这个链表是回文链表。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL){return NULL;}struct ListNode* cur=head;struct ListNode* newnode=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newnode;newnode=cur;cur=next;}return newnode;}struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast=head;struct ListNode* slow=head;while(fast  && fast->next)//当元素是奇数个时fast->next为NULL;当元素为偶数个fast为NULL是结束标志{fast=fast->next->next;slow=slow->next;}return slow;
}class PalindromeList {
public:bool chkPalindrome(ListNode* head) {struct ListNode* mid=middleNode(head);//找到中间节点struct ListNode* rhead=reverseList(mid);//反转中间节点后的元素while(rhead){if(head->val==rhead->val){head=head->next;rhead=rhead->next;}else{return false;//不相等说明不是回文}}return true;}
};

Topic 7:

相交链表

160. 相交链表 - 力扣(LeetCode)

怎么判断链表相交,我们需要看链表的地址是否有相等的,如果我们利用两个for循环来实现判断是否有相等的地址,我们的时间复杂度就是O(N^2),,这个时间复杂度是很大的。我们还能通过什么方法来判断呢?相交的链表有共同的特点,就是它们有共同的尾,我们只需要判断尾的地址是否相等就好,如果尾的地址相等,我们就说明它们是相交的链表。

相交的链表,如何寻找第一个交点,全部遍历一遍,这个好像不太可能。既然链表有交点,第一个交点到链表尾的距离相等,而头到链表交点的距离就不一定相等了,它们的差值刚刚好是两个链表距离的差值。我们让长链表先走它们的差值,然后一起走,等它们的地址相等的时候就是它们的第一个交点。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* cur1=headA;struct ListNode* cur2=headB;int n1=1;//赋值1是因为统计链表长度的时候,我们的最后的一个位置,我们统计到int n2=1;while(cur1->next)//找headA的尾{cur1=cur1->next;++n1;}while(cur2->next)//找headB的尾{cur2=cur2->next;++n2;}if(cur1!=cur2){return NULL;}int dif=abs(n1-n2);//让长的先走cur1=headA;cur2=headB;if(n1>n2){while(dif){cur1=cur1->next;dif--;}}else{while(dif){cur2=cur2->next;dif--;}}while(cur1!=cur2){cur1=cur1->next;cur2=cur2->next;}return cur1;}

相关文章:

手撕单链表练习

Topic 1:LeetCode——203. 移除链表元素203. 移除链表元素 - 力扣(LeetCode)移除链表中的数字6操作很简单,我们只需要把2的指向地址修改就好了,原来的指向地址是6现在改为3这个思路是完全正确的,但是在链表…...

Kubuntu安装教程

文章目录Kubuntu介绍下载Kubuntu在VMware虚拟机中安装Kubuntu1. 点击“创建新的虚拟机”2. 选择“自定义(高级)”3. 按照下图所示进行设置设置网络4. 点击“自定义硬件”5. 开启虚拟机6. 进入安装界面,选择中文,之后点击“安装Kub…...

[蓝桥杯] 树状数组与线段树问题(C/C++)

文章目录 一、动态求连续区间和 1、1 题目描述 1、2 题解关键思路与解答 二、数星星 2、1 题目描述 2、2 题解关键思路与解答 三、数列区间最大值 3、1 题目描述 3、2 题解关键思路与解答 标题:树状数组与线段树问题 作者:Ggggggtm 寄语:与其…...

Matlab-Loma Prieta 地震分析

此示例说明如何将带时间戳的地震数据存储在时间表中以及如何使用时间表函数来分析和可视化数据。 加载地震数据 示例文件quake.mat包含 1989 年 10 月 17 日圣克鲁斯山脉 Loma Prieta 地震的 200 Hz 数据。这些数据由加州大学圣克鲁斯分校查尔斯F里希特地震实验室的 Joel Yelli…...

Spring Boot全局异常处理

使用注解方式处理全局异常使用 ControllerAdvice (RestControllerAdvice) 配合 ExceptionHandler适用于返回数据的请求(一般是RESTful接口规范下的JSON报文)package com.example.exception;import org.slf4j.Logger; import org.s…...

websocket每隔5秒给服务端send一次信息

websocket轮询每隔5秒给服务端send一次信息,主要功能点如下:socket 采用了定时器 setInterval() 需要清除定时器否则会报错监听了突然关闭浏览器窗口,destroyed里面直接监听 window.removeEventListener("beforeu…...

2023年中职网络安全——SQL注入测试(PL)解析

SQL注入测试(PL) 任务环境说明: 服务器场景:Server2312服务器场景操作系统:未知(关闭链接)已知靶机存在网站系统,使用Nmap工具扫描靶机端口,并将网站服务的端口号作为Flag(形式:Flag字符串)值提交。访问网站/admin/pinglun.asp页面,此页面存在SQL注入漏洞,使用排…...

利用蜜罐捕捉攻击实验(31)

预备知识 1、蜜罐的含义和作用 蜜罐(Honeypot)是一种在互联网上运行的计算机系统。它是专门为吸引并诱骗那些试图非法闯入他人计算机系统的人(如电脑黑客)而设计的,蜜罐系统是一个包含漏洞的诱骗系统,它通过模拟一个或多个易受攻击的主机&#xff…...

PyTorch深度学习实战 | 自然语言处理与强化学习

PyTorch是当前主流深度学习框架之一,其设计追求最少的封装、最直观的设计,其简洁优美的特性使得PyTorch代码更易理解,对新手非常友好。本文主要介绍深度学习领域中自然语言处理与强化学习部分。自然语言区别于计算机所使用的机器语言和程序语…...

测牛学堂:接口测试基础理论和工具的使用

接口测试流程总结 1 需求分析,看产品经理的需求文档 2 接口文档解析,开发编写的api接口文档 3 设计测试用例 4脚本开发 5 执行及缺陷跟踪 6 生成测试报告 7接口自动化持续集成 测试解析接口文档 接口文档,又称为api文档,是由后…...

定长内存池的实现

解决的是固定大小的内存申请释放需求&#xff1a; 性能达到极致不考虑内存碎片问题(统一使用自由链表管理还回来的空间) 为了避免命名污染&#xff0c;不要直接using namespace std;只展开常用的。 #include <iostream> using std::cout; using std::endl;申请空间时有…...

三更草堂springSecurity的学习

源码地址&#xff1a;学习springSecurity (gitee.com) git&#xff1a;https://gitee.com/misszyg/spring-security.git 一&#xff0c;认证流程 1&#xff0c;经过UsernamePasswordAuthenticationFilter &#xff08;1&#xff09;传入了用户的账号&#xff0c;密码 源码&a…...

【C语言】指针的深度理解(一)

前言 我们已经了解了指针的概念&#xff0c;一是指针变量是用来存放地址的&#xff0c;每个地址都对应着唯一的内存空间。二是指针的大小是固定的4或8个字节&#xff08;取决于操作系统&#xff0c;32位的占4个字节&#xff0c;64位的占8个字节&#xff09;。三是指针是有类型…...

Kafka最佳实践

前言 Kafka 最佳实践&#xff0c;涉及 典型使用场景Kafka 使用的最佳实践 Kafka 典型使用场景 Data Streaming Kafka 能够对接到 Spark、Flink、Flume 等多个主流的流数据处理技术。利用 Kafka 高吞吐量的特点&#xff0c;客户可以通过 Kafka 建立传输通道&#xff0c;把应…...

入门教程: 认识 React用于构建用户界面的 JavaScript 库

课前准备 我们将会在这个教程中开发一个小游戏。你可能并不打算做游戏开发,然后就直接跳过了这个教程——但是不妨尝试一下!你将在该教程中学到关于构建 React 应用的基础知识,掌握这些知识后,你将会对 React 有更加深刻的理解。 这篇教程分为以下几个部分: 环境准备是学…...

极紫外光源高次谐波发生腔不同区域真空度精密控制解决方案

摘要&#xff1a;在高次谐波发生器中一般包含两个不同真空区域&#xff0c;一个是1~100Torr绝压范围的气池内部的低真空区域&#xff0c;一个是高阶谐波光路上的绝压为0.001Pa量级的高真空区域。本文针对此两个区域的真空度控制提出了相应的解决方案&#xff0c;特别是详细介绍…...

「Vue面试题」在vue中为什么data属性是一个函数而不是一个对象

文章目录一、实例和组件定义data的区别二、组件data定义函数与对象的区别三、原理分析四、结论一、实例和组件定义data的区别 vue实例的时候定义data属性既可以是一个对象&#xff0c;也可以是一个函数 const app new Vue({el:"#app",// 对象格式data:{foo:"…...

如何使用 ChatGPT 编写 SQL JOIN 查询

通过清晰的示例和解释&#xff0c;本文展示了 ChatGPT 如何简化和简化创建复杂 MySQL 查询的过程&#xff0c;使用户更容易与数据库交互并检索他们需要的数据。无论您是初学者还是经验丰富的开发人员&#xff0c;本文都提供了有关如何利用 ChatGPT 来增强您的 MySQL 查询编写技…...

vue2+elementUI完成添加学生删除学生案列

效果图&#xff1a; 点击添加学生按钮&#xff0c;弹出Dialog,收集用户信息&#xff1a; el-table中自定义复选框&#xff0c;选中一行&#xff0c;可以点击删除 代码区域&#xff1a;就一个HTML文件 <!DOCTYPE html> <html lang"en"> <head>&…...

对void的深度理解

作者&#xff1a;小树苗渴望变成参天大树 作者宣言&#xff1a;认真写好每一篇博客 作者gitee:gitee 如 果 你 喜 欢 作 者 的 文 章 &#xff0c;就 给 作 者 点 点 关 注 吧&#xff01; void前言一、 void 关键字二、 void修饰函数返回值和参数三、void指针3.1void * 定义的…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...