【数据结构】链表OJ题
目录
- 面试题 02.04 分割链表
- 剑指 Offer II 027 回文链表
- 160 相交链表
- 141 环形链表
- 142 环形链表 II
- 138 复制带随机指针的链表
面试题 02.04 分割链表
- 定义lesshead和greaterhead链接小于和大于等于k的值
- 分别设置哨兵位和尾节点指针
- 最后将两表去除哨兵位再链接

struct ListNode* partition(struct ListNode* head, int x)
{struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));lesstail->next = NULL;greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));greatertail->next = NULL;struct ListNode* cur = head;while (cur){if (cur->val < x){lesstail->next = cur;lesstail = cur;}else{greatertail->next = cur;greatertail = cur;}cur = cur->next;}lesstail->next = greaterhead->next;greatertail->next = NULL;struct ListNode* newhead = lesshead->next;free(lesshead);free(greaterhead);return newhead;
}
剑指 Offer II 027 回文链表
- 先找到链表中间节点
- 将中间节点以后的节点从原链表截断逆置生成新链表
- 与原链表逐节点的值相比较

//回文结构
bool isPalindrome(struct ListNode* head) {if (head == NULL){return false;}//找中间节点struct ListNode* cur = head, * slow = head, * fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}struct ListNode* mid = slow;//将中间节点之后的顺序反转struct ListNode* newhead = slow;cur = newhead;struct ListNode* prev = NULL;while (cur){struct ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;}newhead = prev;//遍历两组链表,检查是否每位相等struct ListNode* cur2 = newhead;struct ListNode* cur1 = head;while (cur1 && cur2){if (cur1->val != cur2->val){return false;}cur1 = cur1->next;cur2 = cur2->next;}return true;
}
160 相交链表
- 根据两链表长度求出长度差k
- 较长的链表先走k步
- 两表再一起走,节点地址相同时返回此节点
int ListSize(struct ListNode * head){struct ListNode * cur=head;int len=0;while(cur){len++;cur=cur->next;}return len;}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int len1=ListSize(headA);int len2=ListSize(headB);int k=abs(len1-len2);struct ListNode * longlist=headA;struct ListNode * shortlist=headB;if(len1<len2){longlist=headB;shortlist=headA;}struct ListNode * cur1=longlist, *cur2=shortlist;while(k--){cur1=cur1->next;}while(cur1 && cur2){if(cur1==cur2){return cur1;}cur1=cur1->next;cur2=cur2->next;}return NULL;
}
141 环形链表
快慢指针法,相遇则为环形链表
//环形链表,快慢指针法
bool hasCycle(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (slow == fast){return true;}}return false;
}
142 环形链表 II
- 先找到入环点
- 相遇点到入环点的距离等于链头到入环点的距离
- 从链头和相遇点出发,相遇点即为入环点

//环形链表 II
//找到入环点,再判断环形链表代码块内续写
struct ListNode* detectCycle(struct ListNode* head) {struct ListNode* slow = head, * fast = head, * meet = NULL;while (fast && fast->next){//找到快慢指针相遇点fast = fast->next->next;slow = slow->next;//相遇点到入环点的距离等于链头到入环点的距离if (slow == fast){meet = slow;while (meet != head){meet = meet->next;head = head->next;}return meet;}}return NULL;
}
138 复制带随机指针的链表
- 在原链表每个节点后复制一个节点
- 根据原节点设置复制节点的random
- 注意不可复制节点的同时处理random,因为random指向位置还未完成复制
- 将处理好的复制节点链接到newhead

//复制带随机指针的链表
struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;//在原链表每个节点后复制一个节点while (cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}cur = head;struct Node* next = NULL;//根据原节点设置复制节点的randomwhile (cur){struct Node* copy = cur->next;next = copy->next;if (cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = next;}//将处理好的复制节点链接到newheadcur = head;struct Node* newtail = NULL, * newhead = NULL;while (cur){struct Node* copy = cur->next;next = copy->next;if (newtail == NULL){newhead = newtail = copy;}else{newtail->next = copy;newtail = copy;}cur->next = next;cur = next;}return newhead;
}
相关文章:
【数据结构】链表OJ题
目录面试题 02.04 分割链表剑指 Offer II 027 回文链表160 相交链表141 环形链表142 环形链表 II138 复制带随机指针的链表面试题 02.04 分割链表 定义lesshead和greaterhead链接小于和大于等于k的值分别设置哨兵位和尾节点指针最后将两表去除哨兵位再链接 struct ListNode* p…...
冒泡 VS 插入 VS 选择——谁更胜一筹?(附排序源码)
文章目录什么样的“排序算法”更加优质?排序算法的执行效率排序算法的内存消耗排序算法的稳定性冒泡排序(Bubble Sort)插入排序(Insertion Sort)选择排序(Selection Sort)最终的胜利者…...
[python tools] 今天看到另一个配置工具 YACS,所以做下笔记
YACS 实际上就只是把别人的readme翻译了一下 github: https://github.com/rbgirshick/yacs 样例代码: https://github.com/Wuziyi616/multi_part_assembly/blob/master/docs/config.md 一、使用方法 1. 首先搞一个config的python文件,用来存一下基本的配置信息 比…...
Prometheus cadvisor容器监控和node-exporter节点监控
往期文章 Prometheus监控系统 https://blog.csdn.net/qq_39578545/article/details/108754585 Docker之compose介绍 使用一个Dockerfile模板文件可以定义一个单独的应用容器,如果需要定义多个容器就需要服务编排。下面介绍Docker官方产品,Docker Comp…...
机器学习|正则化|评估方法|分类模型性能评价指标|吴恩达学习笔记
前文回顾:逻辑回归 目录 📚正则化 🐇过拟合的问题 🐇代价函数 🐇正则化线性回归 🐇正则化的逻辑回归模型 📚模型评估方法 🐇留出法(hold-out) &#…...
python迭代器详解
不懂的问题:什么是协变、逆变?渐进式? _T_co TypeVar("_T_co", covariantTrue) # Any type covariant containers.作者:20岁爱吃必胜客(坤制作人),近十年开发经验, 跨域学习者&…...
关于Docker逃逸
关于Docker逃逸 文章目录关于Docker逃逸前言一、判断是否为docker容器?二、privileged特权模式启动容器逃逸三、 Docker Remote API未授权访问逃逸四、危险挂载导致Docker逃逸五、危险挂载Docker Socket逃逸六、 挂载宿主机procfs逃逸七、脏牛漏洞来进行docker逃逸八…...
@Autowired和@Resource区别
Autowired和Resource到底有什么区别 Autowired 和 Resource 都是用来实现依赖注入的注解(在 Spring/Spring Boot 项目中),但二者却有着 5 点不同: 来源不同:Autowired 来自 Spring 框架,而 Resource 来自…...
动态内存管理详细讲解
目录 1.为什么存在动态内存分配 2. 动态内存函数的介绍 2.1 malloc和free 2.2 calloc 2.3 realloc 今天要和大家分享的内容是的动态内存管理,我们先从他的定义入手学习。 1.为什么存在动态内存分配 我们到现在已经掌握了内存开辟的方式就是要么创建一个变量…...
Python和Excel的完美结合:常用操作汇总(案例详析)
在以前,商业分析对应的英文单词是Business Analysis,大家用的分析工具是Excel,后来数据量大了,Excel应付不过来了(Excel最大支持行数为1048576行),人们开始转向python和R这样的分析工具了&#…...
卡特兰数、斯特林数基础
卡特兰数 从格点(0,0)(0,0)(0,0)走到格点(n,n)(n,n)(n,n),只能向右或向上走,不能穿过对角线,的路径的条数,称为卡特兰数HnH_nHn。 则有H01H_01H01。 通项公式: Hn(2nn)−(2nn−1)H_n\begin{pmatrix} 2n\\ n \en…...
STL——mapmultimap和setmultiset
一、关联式容器 与序列式容器相同,关联式容器也是用于存储数据的,不同的是,关联式容器里存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。 二、键值对 用来表示具有一一对应的一种结构,该…...
2023热门抖音权重查询小程序源码
2023热门抖音权重查询小程序源码 跟抖音上很火的一模一样,小程序适配优化。接口免费。小程序不是网页 修改教程: 1,如果想修改或者去除水印,直接删除或修改“index.html”12~22行 2,如果想修改logo,直接…...
153.网络安全渗透测试—[Cobalt Strike系列]—[生成hta/exe/宏后门]
我认为,无论是学习安全还是从事安全的人多多少少都会有些许的情怀和使命感!!! 文章目录一、后门简介1、hta后门2、exe后门3、宏病毒后门二、生成后门并测试0、测试环境1、生成hta后门并测试2、生成exe后门并测试3、生成宏病毒后门…...
如何成为优秀的程序员
崔宝秋,现任小米首席架构师、小米云平台负责人。1995年赴美留学,纽约州立大学石溪分校计算机科学系博士毕业,曾任IBM高级工程师和高级研发经理、雅虎搜索技术核心团队主任工程师、LinkedIn主任工程师,2012年回国加入小米科技。 20…...
多线程(四):线程安全
在开始讲解线程安全之前我们先来回顾一下我们学了那些东西了: 1. 线程和进程的认识 2. Thread 类的基本用法 3. 简单认识线程状态 4. 初见线程安全 上一章结束时看了一眼线程安全问题,本章将针对这个重点讲解。 一个代码在单线程中能够安全执行&am…...
[ROC-RK3568-PC] [Firefly-Android] 10min带你了解Camera的使用
🍇 博主主页: 【Systemcall小酒屋】🍇 博主追寻:热衷于用简单的案例讲述复杂的技术,“假传万卷书,真传一案例”,这是林群院士说过的一句话,另外“成就是最好的老师”,技术…...
C++之模拟实现string
文章目录前言一、包含的相关头文件二、构造和析构1.构造函数2.拷贝构造1.传统写法2.现代写法3.赋值运算符重载1.传统写法2.现代写法4.析构函数三、iterator四、modify1.push_back(尾插一个字符)2.append(尾插一个字符串)3.运算符重载1.尾插字…...
SpringBoot实战(十三)集成 Admin
目录一、简介二、搭建 springboot-admin 管理服务1.Maven 依赖2.application.yml3.添加 EnableAdminServer4.启动服务,查看页面三、搭建 springboot-admin-client 客户端服务1.Maven 依赖2.application.yml3.启动服务,查看页面四、搭配 Eureka 使用1.搭建…...
mke2fs命令:建立ext2文件系统
以下内容源于网络资源的学习与整理,如有侵权请告知删除。 使用格式 mke2fs [options] [设备名称] [区块数] options与含义 -c:检查是否有损坏的区块。-F:不管指定的设备为何,强制执行mke2fs。-M:记录最后一次挂入的…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)
名人说:莫道桑榆晚,为霞尚满天。——刘禹锡(刘梦得,诗豪) 原创笔记:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 上一篇:《数据结构第4章 数组和广义表》…...
leetcode73-矩阵置零
leetcode 73 思路 记录 0 元素的位置:遍历整个矩阵,找出所有值为 0 的元素,并将它们的坐标记录在数组zeroPosition中置零操作:遍历记录的所有 0 元素位置,将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...
