首页/新闻资讯/正文详情

链表中级应用:两两交换、删除倒数节点与相交问题

发布时间:2026/11/4 23:40:32 来源:云帆数科 栏目:资讯中心
链表中级应用:两两交换、删除倒数节点与相交问题
1. 链表基础回顾与训练营目标在算法学习过程中链表是必须攻克的基础数据结构之一。相比数组的连续存储特性链表通过节点和指针实现非连续存储这种差异带来了完全不同的操作方式和性能特点。今天的训练内容聚焦链表的中级应用场景主要解决以下三类典型问题两两交换链表中的节点LeetCode 24删除链表的倒数第N个节点LeetCode 19链表相交问题LeetCode 面试题 02.07提示建议先独立完成链表基本操作的代码实现如节点定义、遍历、增删改查再进入今天的主题练习。1.1 链表操作的性能特点链表操作的核心在于指针控制。与数组相比插入/删除时间复杂度O(1)已知位置时随机访问时间复杂度O(n)空间复杂度O(n) 指针额外空间# 单链表节点标准定义 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next2. 两两交换链表节点LeetCode 242.1 问题重述与示例给定链表1-2-3-4要求返回2-1-4-3。需要实际修改节点连接关系而非仅交换值。2.2 迭代解法详解关键点在于维护三个指针pre已处理部分的尾节点first待交换的第一个节点second待交换的第二个节点def swapPairs(head: ListNode) - ListNode: dummy ListNode(0, head) # 虚拟头节点简化边界处理 pre, curr dummy, head while curr and curr.next: # 保存节点引用 first curr second curr.next next_pair second.next # 执行交换 pre.next second second.next first first.next next_pair # 移动指针 pre first curr next_pair return dummy.next2.3 递归解法分析递归思路更简洁但空间复杂度为O(n)基线条件当前节点或下一节点为空递归单元交换前两个节点并连接后续递归结果def swapPairs(head: ListNode) - ListNode: if not head or not head.next: return head new_head head.next head.next swapPairs(new_head.next) new_head.next head return new_head2.4 易错点警示指针丢失交换时未保存next_pair会导致链表断裂边界处理奇数长度链表最后一个节点不需处理虚拟头节点建议始终使用以避免头节点特殊处理3. 删除链表倒数第N个节点LeetCode 193.1 双指针经典解法快慢指针法是该问题的标准解法步骤如下快指针先走n步快慢指针同步移动直到快指针到达末尾此时慢指针指向待删除节点的前驱def removeNthFromEnd(head: ListNode, n: int) - ListNode: dummy ListNode(0, head) slow fast dummy # 快指针先走n步 for _ in range(n): fast fast.next # 同步移动直到末尾 while fast.next: slow slow.next fast fast.next # 删除节点 slow.next slow.next.next return dummy.next3.2 边界条件处理链表长度等于n时需删除头节点空链表或n0的特殊情况n大于链表长度时的处理题目通常保证n有效3.3 复杂度分析时间复杂度O(L) 一次遍历空间复杂度O(1)4. 链表相交问题LeetCode 面试题 02.074.1 问题本质理解判断两个链表是否相交即是否存在共享的节点内存地址相同。注意不是值相等。4.2 双指针解法关键思路让两个指针走相同的总路程lenA lenBdef getIntersectionNode(headA: ListNode, headB: ListNode) - ListNode: p1, p2 headA, headB while p1 ! p2: p1 p1.next if p1 else headB p2 p2.next if p2 else headA return p14.3 数学证明设链表A独立部分长a链表B独立部分长b公共部分长c指针1路程a c b指针2路程b c a会在第二轮的公共节点处相遇4.4 注意事项必须比较节点对象而非节点值无相交时应返回None而非任何特殊值链表可能包含环本题假设无环5. 链表问题通用解题技巧5.1 虚拟头节点(Dummy Node)几乎所有链表问题都可以通过引入dummy节点简化避免头节点特殊处理统一空链表情况方便返回结果链表头dummy ListNode(0, head) # ...处理逻辑... return dummy.next5.2 指针操作四要素指针移动条件如fast.next不为空移动步数控制如先走n步终止条件判断指针重置规则如到达末尾后跳转到另一链表头5.3 调试建议绘制链表和指针位置示意图使用小规模测试用例如3-5个节点检查指针操作前后的链表状态6. 进阶挑战与扩展思考6.1 K个一组翻转链表将两两交换扩展为K个节点一组翻转LeetCode 25先计算链表长度按组处理每组内执行标准翻转连接各组之间的边界6.2 带环链表检测使用快慢指针检测环LeetCode 141快指针每次两步慢指针每次一步相遇则有环快指针到末尾则无环6.3 复杂链表复制包含随机指针的链表复制LeetCode 138在原节点后插入复制节点设置random指针拆分两个链表7. 训练建议与学习路线7.1 刻意练习方案第一阶段手写标准链表操作30分钟第二阶段闭眼默写三道题的解法1小时第三阶段修改条件变种练习如交换相邻K个节点7.2 常见面试考察点指针操作的代码实现能力边界条件处理完整性时间/空间复杂度分析递归与迭代的转换能力7.3 推荐扩展题库合并两个有序链表LeetCode 21反转链表IILeetCode 92重排链表LeetCode 143回文链表LeetCode 234链表操作的熟练度直接影响到后续树形结构和图算法的学习效果。建议每天保持至少30分钟的专项练习持续2周后可明显提升指针操作的手感。在实际编写代码时建议先用注释写出指针移动逻辑再转化为具体代码这种方法能有效减少指针丢失错误。

相关推荐

DM7客户端WIN64安装配置全攻略:环境准备、连接调优与避坑指南
DM7客户端WIN64安装配置全攻略:环境准备、连接调优与避坑指南

简介:DM7客户端工具WIN64是面向数据库管理员与开发人员的图形化数据库管理软件,用于在64位Windows环境下连接、管理与维护达梦数据库管理系统V7。工具覆盖数据库连接配置、SQL编辑与调试、表与视图管理、存储过程与函数维护、用户权限设置、数据导入导出… · 2026/11/4 23:39:26

零样本语音克隆技术原理与工程实践
零样本语音克隆技术原理与工程实践

我理解您的要求,但需要说明:您提供的输入内容中,项目标题虽已给出,但项目正文、关键词、摘要描述均为空,且后续未附任何实质性背景信息(如工具名称、技术原理、开源地址、功能特性、使用场景等)… · 2026/11/4 23:39:26

3秒声音克隆技术原理与实战指南
3秒声音克隆技术原理与实战指南

1. 项目概述:声音克隆不是魔法,但这次它真的“神”了“又一个神级声音克隆工具——暴涨3.3万Star”,这个标题在技术圈刷屏时,我正调试着自己搭的第四个语音合成Pipeline。说实话,第一反应是皱眉:近几年“神… · 2026/11/4 23:39:26

请求头改写失效:搜索区域判定的多信号一致性校验与工程化替代
请求头改写失效:搜索区域判定的多信号一致性校验与工程化替代

1. 先把现象拆开:一次"改请求头失效"到底发生了什么做爬虫、做搜索聚合、做浏览器扩展的同行,最近应该都碰到过同一类反馈:原本靠自定义Accept-Language、User-Agent、Referer这几项请求头就能把搜索服务的返回结果切到国际版&… · 2026/11/5 6:01:15

GitHub镜像站搭建全攻略:从需求分析到性能优化
GitHub镜像站搭建全攻略:从需求分析到性能优化

1. GitHub镜像站搭建全攻略作为一名长期在代码托管平台工作的开发者,我深刻理解国内访问GitHub时遇到的种种困扰。从2016年开始,我先后为三家科技公司搭建过内部GitHub镜像服务,期间踩过不少坑,也积累了大量实战经验。本文将分享一… · 2026/11/5 6:01:15

免费资源网站避坑指南:十类素材站点与收藏维护方法
免费资源网站避坑指南:十类素材站点与收藏维护方法

1. 收藏夹里躺着的链接,为什么九成都没再打开过上个月接了个急活,要在两天内出一版产品介绍页。图片、图标、字体、背景音乐全得自己找,我打开收藏夹里那个叫"资源"的文件夹,里面躺着上百个号称免费实用的资源网站&… · 2026/11/5 6:01:15

HAP包体臃肿优化实战:从诊断到瘦身的完整方案
HAP包体臃肿优化实战:从诊断到瘦身的完整方案

1. 从HAP包体臃肿现象说起最近在技术社区看到不少开发者吐槽:"为什么我的HAP安装包越做越大?明明没加多少功能,体积却膨胀了好几倍!"这让我想起上周排查的一个典型案例:某金融类App的HAP包从最初的25MB猛增到… · 2026/11/5 6:01:15

高防IP接入后502错误排查:反向代理回源链路与配置
高防IP接入后502错误排查:反向代理回源链路与配置

上周凌晨两点多被电话叫起来,说业务站全站 502,值班的 A 同学第一反应是重启应用,重启完还是 502,第二反应是回滚代码,回滚完依旧 502。后来一查,当晚正好是新接的高防 IP 完成解析生效的时间点。把回源配置… · 2026/11/5 6:01:15

RabbitMQ消息投递可靠性保障与实战优化
RabbitMQ消息投递可靠性保障与实战优化

1. 消息队列中的投递可靠性难题在分布式系统中,RabbitMQ作为消息中间件的核心组件,其消息投递的可靠性直接关系到业务一致性。我经历过一个电商订单系统案例:促销期间由于消息丢失导致10%的订单未触发库存扣减,直接造成超卖事故。… · 2026/11/5 6:00:15

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码