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

【数据结构】链表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 选择——谁更胜一筹?(附排序源码)

文章目录什么样的“排序算法”更加优质&#xff1f;排序算法的执行效率排序算法的内存消耗排序算法的稳定性冒泡排序&#xff08;Bubble Sort&#xff09;插入排序&#xff08;Insertion Sort&#xff09;选择排序&#xff08;Selection Sort&#xff09;最终的胜利者&#x1f…...

[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文件&#xff0c;用来存一下基本的配置信息 比…...

Prometheus cadvisor容器监控和node-exporter节点监控

往期文章 Prometheus监控系统 https://blog.csdn.net/qq_39578545/article/details/108754585 Docker之compose介绍 使用一个Dockerfile模板文件可以定义一个单独的应用容器&#xff0c;如果需要定义多个容器就需要服务编排。下面介绍Docker官方产品&#xff0c;Docker Comp…...

机器学习|正则化|评估方法|分类模型性能评价指标|吴恩达学习笔记

前文回顾&#xff1a;逻辑回归 目录 &#x1f4da;正则化 &#x1f407;过拟合的问题 &#x1f407;代价函数 &#x1f407;正则化线性回归 &#x1f407;正则化的逻辑回归模型 &#x1f4da;模型评估方法 &#x1f407;留出法&#xff08;hold-out&#xff09; &#…...

python迭代器详解

不懂的问题&#xff1a;什么是协变、逆变&#xff1f;渐进式&#xff1f; _T_co TypeVar("_T_co", covariantTrue) # Any type covariant containers.作者&#xff1a;20岁爱吃必胜客&#xff08;坤制作人&#xff09;&#xff0c;近十年开发经验, 跨域学习者&…...

关于Docker逃逸

关于Docker逃逸 文章目录关于Docker逃逸前言一、判断是否为docker容器&#xff1f;二、privileged特权模式启动容器逃逸三、 Docker Remote API未授权访问逃逸四、危险挂载导致Docker逃逸五、危险挂载Docker Socket逃逸六、 挂载宿主机procfs逃逸七、脏牛漏洞来进行docker逃逸八…...

@Autowired和@Resource区别

Autowired和Resource到底有什么区别 Autowired 和 Resource 都是用来实现依赖注入的注解&#xff08;在 Spring/Spring Boot 项目中&#xff09;&#xff0c;但二者却有着 5 点不同&#xff1a; 来源不同&#xff1a;Autowired 来自 Spring 框架&#xff0c;而 Resource 来自…...

动态内存管理详细讲解

目录 1.为什么存在动态内存分配 2. 动态内存函数的介绍 2.1 malloc和free 2.2 calloc 2.3 realloc 今天要和大家分享的内容是的动态内存管理&#xff0c;我们先从他的定义入手学习。 1.为什么存在动态内存分配 我们到现在已经掌握了内存开辟的方式就是要么创建一个变量…...

Python和Excel的完美结合:常用操作汇总(案例详析)

在以前&#xff0c;商业分析对应的英文单词是Business Analysis&#xff0c;大家用的分析工具是Excel&#xff0c;后来数据量大了&#xff0c;Excel应付不过来了&#xff08;Excel最大支持行数为1048576行&#xff09;&#xff0c;人们开始转向python和R这样的分析工具了&#…...

卡特兰数、斯特林数基础

卡特兰数 从格点(0,0)(0,0)(0,0)走到格点(n,n)(n,n)(n,n)&#xff0c;只能向右或向上走&#xff0c;不能穿过对角线&#xff0c;的路径的条数&#xff0c;称为卡特兰数HnH_nHn​。 则有H01H_01H0​1。 通项公式&#xff1a; Hn(2nn)−(2nn−1)H_n\begin{pmatrix} 2n\\ n \en…...

STL——mapmultimap和setmultiset

一、关联式容器 与序列式容器相同&#xff0c;关联式容器也是用于存储数据的&#xff0c;不同的是&#xff0c;关联式容器里存储的是<key, value>结构的键值对&#xff0c;在数据检索时比序列式容器效率更高。 二、键值对 用来表示具有一一对应的一种结构&#xff0c;该…...

2023热门抖音权重查询小程序源码

2023热门抖音权重查询小程序源码 跟抖音上很火的一模一样&#xff0c;小程序适配优化。接口免费。小程序不是网页 修改教程: 1&#xff0c;如果想修改或者去除水印&#xff0c;直接删除或修改“index.html”12&#xff5e;22行 2&#xff0c;如果想修改logo&#xff0c;直接…...

153.网络安全渗透测试—[Cobalt Strike系列]—[生成hta/exe/宏后门]

我认为&#xff0c;无论是学习安全还是从事安全的人多多少少都会有些许的情怀和使命感&#xff01;&#xff01;&#xff01; 文章目录一、后门简介1、hta后门2、exe后门3、宏病毒后门二、生成后门并测试0、测试环境1、生成hta后门并测试2、生成exe后门并测试3、生成宏病毒后门…...

如何成为优秀的程序员

崔宝秋&#xff0c;现任小米首席架构师、小米云平台负责人。1995年赴美留学&#xff0c;纽约州立大学石溪分校计算机科学系博士毕业&#xff0c;曾任IBM高级工程师和高级研发经理、雅虎搜索技术核心团队主任工程师、LinkedIn主任工程师&#xff0c;2012年回国加入小米科技。 20…...

多线程(四):线程安全

在开始讲解线程安全之前我们先来回顾一下我们学了那些东西了&#xff1a; 1. 线程和进程的认识 2. Thread 类的基本用法 3. 简单认识线程状态 4. 初见线程安全 上一章结束时看了一眼线程安全问题&#xff0c;本章将针对这个重点讲解。 一个代码在单线程中能够安全执行&am…...

[ROC-RK3568-PC] [Firefly-Android] 10min带你了解Camera的使用

&#x1f347; 博主主页&#xff1a; 【Systemcall小酒屋】&#x1f347; 博主追寻&#xff1a;热衷于用简单的案例讲述复杂的技术&#xff0c;“假传万卷书&#xff0c;真传一案例”&#xff0c;这是林群院士说过的一句话&#xff0c;另外“成就是最好的老师”&#xff0c;技术…...

C++之模拟实现string

文章目录前言一、包含的相关头文件二、构造和析构1.构造函数2.拷贝构造1.传统写法2.现代写法3.赋值运算符重载1.传统写法2.现代写法4.析构函数三、iterator四、modify1.push_back(尾插一个字符&#xff09;2.append&#xff08;尾插一个字符串&#xff09;3.运算符重载1.尾插字…...

SpringBoot实战(十三)集成 Admin

目录一、简介二、搭建 springboot-admin 管理服务1.Maven 依赖2.application.yml3.添加 EnableAdminServer4.启动服务&#xff0c;查看页面三、搭建 springboot-admin-client 客户端服务1.Maven 依赖2.application.yml3.启动服务&#xff0c;查看页面四、搭配 Eureka 使用1.搭建…...

mke2fs命令:建立ext2文件系统

以下内容源于网络资源的学习与整理&#xff0c;如有侵权请告知删除。 使用格式 mke2fs [options] [设备名称] [区块数] options与含义 -c&#xff1a;检查是否有损坏的区块。-F&#xff1a;不管指定的设备为何&#xff0c;强制执行mke2fs。-M&#xff1a;记录最后一次挂入的…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...