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

【数据结构初阶】链表OJ

链表OJ

    • 题目一:移除链表元素
    • 题目二:反转链表
    • 题目三:链表的中间节点
    • 题目四:链表中倒数第k个结点
    • 题目五:合并两个有序链表
    • 题目六:链表分割
    • 题目七:链表的回文结构
    • 题目八:相交链表
    • 题目九:环形链表
    • 题目十:环形链表II

题目一:移除链表元素

OJ
在这里插入图片描述
方案一:

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, * prev = NULL;while (cur){if (cur->val == val){if (cur == head){head = cur->next;free(cur);cur = head;}else{prev->next = cur->next;free(cur);cur = prev->next;}}else{prev = cur;cur = cur->next;}}return head;
}

方案二:

题目解析:把原链表遍历一遍,插入新链表
在这里插入图片描述

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* newnode = NULL, * tail = NULL;struct ListNode* cur = head;while (cur){if (cur->val == val){struct ListNode* del = cur;cur = cur->next;free(del);}else{if (tail == NULL){newnode = tail = cur;//tail = tail->next;}else{tail->next = cur;tail = tail->next;}cur = cur->next;}}if (tail)tail->next = NULL;return newnode;
}

题目二:反转链表

OJ
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head) 
{struct ListNode* newnode = NULL, * cur = head;while (cur){struct ListNode* next = cur->next;//尾插cur->next = newnode;newnode = cur;cur = next;}return newnode;
}

题目三:链表的中间节点

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{int val;struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

题目四:链表中倒数第k个结点

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) 
{struct ListNode* fast = pListHead, * slow = pListHead;while (k--){if (fast == NULL)return NULL;fast = fast->next;}while (fast){slow = slow->next;fast = fast->next;}return slow;
}

题目五:合并两个有序链表

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{int val;struct ListNode* next;
};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if (list1 == NULL)return list2;if (list2 = NULL)return list1;struct ListNode* tail = NULL, * head = NULL;head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));while (list1 && list2){if (list1->val < list2->val){tail->next = list1;tail = tail->next;list1 = list1->next;}else{tail->next = list2;tail = tail->next;list2 = list2->next;}}if (list1)tail->next = list1;if (list2)tail->next = list2;struct ListNode* del = head;head = head->next;free(del);return head;
}

题目六:链表分割

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
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* lhead, * ltail, * gtail, * ghead;ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;while (cur){if (cur->val < x){ltail->next = cur;ltail = ltail->next;}else{gtail->next = cur;gtail = gtail->next;}cur = cur->next;}ltail->next = ghead->next;gtail->next = NULL;struct ListNode* head = lhead->next;free(lhead);free(ghead);return head;}
};

题目七:链表的回文结构

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode 
{int val;struct ListNode* next;ListNode(int x) : val(x), next(NULL) {}
}; 
class PalindromeList
{
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}struct ListNode* reverseList(struct ListNode* head){struct ListNode* newnode = NULL, * cur = head;while (cur){struct ListNode* next = cur->next;cur->next = newnode;newnode = cur;cur = next;}return newnode;}bool chkPalindrome(ListNode* A){struct ListNode* mid = middleNode(A);struct ListNode* rmid = reverseList(mid);while (A && rmid){if (A->val != rmid->val)return false;A = A->next;rmid = rmid->next;}return true;}
};

题目八:相交链表

OJ
在这里插入图片描述

题目解析:
定义快慢指针,使快指针先走与慢指针同步。然后同时走看是否相交
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{struct ListNode* curA = headA, * curB = headB;int lenA = 1, lenB = 1;while (curA){curA = curA->next;lenA++;}while (curB){curB = curB->next;lenB++;}if (curA != curB)return false;int gab = abs(lenA - lenB);struct ListNode* longest = headA, * shortest = headB;if (lenA < lenB){longest = headB;shortest = headA;}while (gab--){longest = longest->next;}while (shortest != longest){shortest = shortest->next;longest = longest->next;}return longest;
}

题目九:环形链表

OJ

在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode {int val;struct ListNode* next;
};
bool hasCycle(struct ListNode* head)
{struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast)return true;}return false;
}

题目十:环形链表II

OJ
在这里插入图片描述

题目解析:
在这里插入图片描述

代码演示:
struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast){struct ListNode* meet = slow;while(meet != head){head = head->next;meet = meet->next;}return meet;}}return NULL;
}

💘不知不觉,【数据结构初阶】链表OJ以告一段落。通读全文的你肯定收获满满,让我们继续为数据结构学习共同奋进!!!

相关文章:

【数据结构初阶】链表OJ

链表OJ 题目一&#xff1a;移除链表元素题目二&#xff1a;反转链表题目三&#xff1a;链表的中间节点题目四&#xff1a;链表中倒数第k个结点题目五&#xff1a;合并两个有序链表题目六&#xff1a;链表分割题目七&#xff1a;链表的回文结构题目八&#xff1a;相交链表题目九…...

【Vue渲染】 条件渲染 | v-if | v-show | 列表渲染 | v-for

目录 前言 v-if和v-show的区别和联系 v-show和v-if如何选择 条件渲染|v-if|v-show v-if v-if v-else v-if v-else-if v-else template v-show 列表渲染|v-for v-for 前言 本文介绍Vue渲染&#xff0c;包含条件渲染v-if和v-show的区别和联系以及列表渲染v-for v-if和…...

开源网安解决方案荣获四川数实融合创新实践优秀案例

​11月16日&#xff0c;2023天府数字经济峰会在成都圆满举行。本次峰会由四川省发展和改革委员会、中共四川省委网络安全和信息化委员会办公室、四川省经济和信息化厅等部门联合指导&#xff0c;聚焦数字经济与实体经济深度融合、数字赋能经济社会转型发展等话题展开交流研讨。…...

debian/ubuntu/linux如何快速安装vscode

前言 这里写一篇简短的文字用来记录如何在Linux发行版上快速安装VScode&#xff0c;主要使用的一个软件snap&#xff0c;做一个简单介绍&#xff1a; Snap Store 是 Ubuntu、Debian、Fedora 和其他几个 Linux 发行版中的一个应用商店&#xff0c;提供了数千个应用程序和工具的…...

Python3语法总结-数据转换②

Python3语法总结-数据转换② Python3语法总结二.Python数据类型转换隐式类型转换显示类型转换 Python3语法总结 二.Python数据类型转换 有时候我们&#xff0c;需要对数据内置的类型进行转换&#xff0c;数据类型的转换。 Python 数据类型转换可以分为两种&#xff1a; 隐式类…...

【火炬之光-魔灵装备】

文章目录 装备天赋追忆石板技能魂烛刷图策略 装备 头部胸甲手套鞋子武器盾牌项链戒指腰带神格备注盾牌其余的装备要么是召唤物生命&#xff0c;要么是技能等级&#xff0c;鞋子的闪电技能等级加2不是核心&#xff0c;腰带的话主要是要冷却有冷却暗影的技能是不会断的&#xff…...

javascript选择器的封装,只需要写元素名或css类及id都可以选择到元素

//模仿jquery选择器样式&#xff0c;只需要写元素名或css类及id都可以选择到元素 <html><head><meta http-equiv"Content-Type:text/html;charsetutf8"/><link rel"shortcut icon" href"#"/><title>封装选择器&l…...

机器学习第7天:逻辑回归

文章目录 介绍 概率计算 逻辑回归的损失函数 单个实例的成本函数 整个训练集的成本函数 鸢尾花数据集上的逻辑回归 Softmax回归 Softmax回归数学公式 Softmax回归损失函数 调用代码 参数说明 结语 介绍 作用&#xff1a;使用回归算法进行分类任务 思想&#xff1a;…...

努力奋斗,遇上对的人

...

基于单片机音乐弹奏播放DS1302万年历显示及源程序

一、系统方案 1、本设计采用51单片机作为主控器。 2、DS1302计时显示年月日时分秒。 3、按键可以弹奏以及播放音乐&#xff0c;内置16首音乐。 二、硬件设计 原理图如下&#xff1a; 三、单片机软件设计 1、首先是系统初始化 /时钟显示**/ void init_1602_ds1302() { write…...

ceph学习笔记

ceph ceph osd lspoolsrbd ls -p testpool#查看 ceph 集群中有多少个 pool,并且每个 pool 容量及利 用情况 rados dfceph -sceph osd tree ceph dfceph versionsceph osd pool lsceph osd crush rule dumpceph auth print-key client.adminceph orch host lsceph crash lsceph…...

SQLSERVER 遍历循环的两种方式很详细有源码(2)

2.游标循环 Create table WS_Student ( [Id] int primary key not null, [My_Cocode] [int], [My_SCocode] [int], [userId] [bigint], [SetCName] [varchar](50) NULL, [SetEName] [varchar](50) NULL, [SetPcode] [varchar](50) NULL, [Se…...

flutter背景图片设置

本地图片设置 1、在配置文件pubspec.yaml中&#xff0c;设置以下代码 assets:- assets/- assets/test/2、如果目录中没有assets文件夹&#xff0c;则创建一个文件夹&#xff0c;并且取名为assets&#xff0c;在此文件夹中存放图片资源即可&#xff0c;如果想分文件夹管理&…...

【运维 监控】Grafana + Prometheus,监控Linux

安装和配置Grafana与Prometheus需要一些步骤&#xff0c;下面是一个简单的指南&#xff1a; 安装 Prometheus&#xff1a; 使用包管理器安装 Prometheus。在 Debian/Ubuntu 上&#xff0c;可以使用以下命令&#xff1a; sudo apt-get update sudo apt-get install prometheus在…...

Sentinel底层原理(下)

1、概述 Sentinel的核心原理&#xff0c;也就是前面提到暗流涌动的SphU.entry(…)这行代码背后的逻辑。 Sentinel会为每个资源创建一个处理链条&#xff0c;就是一个责任链&#xff0c;第一次访问这个资源的时候创建&#xff0c;之后就一直复用&#xff0c;所以这个处理链条每…...

竞赛选题 疫情数据分析与3D可视化 - python 大数据

文章目录 0 前言1 课题背景2 实现效果3 设计原理4 部分代码5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 大数据全国疫情数据分析与3D可视化 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff0…...

macos 配置ndk环境

选择Android Studio下默认的ndk环境 mac电脑的ndk默认路径一般是 /Users/user_name/Library/Android/sdk/ndk/version_code 其中user_name为自己电脑的用户名&#xff0c;version_code为自己ndk安装的版本号&#xff0c;比如我这里电脑的ndk路径就是 /Users/zhangsan/Libra…...

【linux】进行间通信——共享内存+消息队列+信号量

共享内存消息队列信号量 1.共享内存1.1共享内存的原理1.2共享内存的概念1.3接口的认识1.4实操comm.hppservice.cc &#xff08;写&#xff09;clint.cc &#xff08;读&#xff09; 1.5共享内存的总结1.6共享内存的内核结构 2.消息队列2.1原理2.2接口 3.信号量3.1信号量是什么3…...

PlantUML基础使用教程

环境搭建 IDEA插件下载 打开IEDA系列IDE&#xff0c;从FIle–>Settings–>Plugins–>Marketplace 进入到插件下载界面&#xff0c;搜索PlantUML&#xff0c;安装PlantUML Integration和PlantUML Parser两个插件&#xff0c;并重启IDE 安装和配置Graphviz 进入官网…...

Redis:新的3种数据类型Bitmaps、HyperLoglog、Geographic

目录 Bitmaps简介常用命令bitmaps与set比较 HyperLoglog简介命令 Geographic简介命令 Bitmaps 简介 位操作字符串。 现代计算机使用二进制&#xff08;位&#xff09;作为信息的基本单位&#xff0c;1个字节等于8位&#xff0c;例如“abc”字符串是有3个字节组成&#xff0c…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...