news 2026/5/16 13:38:42

单链表的应用-反转链表and删除链表中间结点

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
单链表的应用-反转链表and删除链表中间结点

反转链表

解法:多指针

1.创建三个指针

  • first:记录当前节点的 “前一个节点”(反转后,当前节点要指向它);
  • second:指向当前正在处理的节点(每轮循环要反转它的next指针);
  • third:暂存second下一个节点(避免反转second的指针后,丢失后续链表)。

2.让third通过箭头移动,而first和second通过赋值移动,first、second、third指针通过循环依次向后挪位置,直至second=NULL

3.当循环结束时,所有的元素都被处理完毕,此时的指向是这样

需要为逆置后的新链表添加一个新的头结点,然后让新头结点的next指向“反转后的首元结点”(即原链表的尾结点first)

整体代码:

删除链表中间结点:快慢指针(fast/slow)

情况1:链表有奇数个结点(中间结点即为(n+1)/2)

情况2:链表有偶数个结点(中间结点为n/2+1)

大致做法:1.创建fast、slow两个指针,让slow指向链表的头结点,让fast指向链表的首元结点

2.fast和slow指针同时移动,fast每次移动两步,slow每次移动一步(fast移动的步长刚好为slow的两倍)

3.当fast=NULL(链表有偶数个结点)或者fast->next=NULL(链表有奇数个结点)时,表明fast已经遍历完整个链表,此时的slow恰好指向中间结点的前一个结点

与题目相关的截图来源于b站逊哥

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/5/13 14:33:02

JavaScript 中的组合模式(Composite Pattern):实现树形结构的统一操作

JavaScript 中的组合模式:实现树形结构的统一操作各位技术爱好者,欢迎来到今天的讲座。我们将深入探讨 JavaScript 中一个极其强大且实用的设计模式——组合模式(Composite Pattern)。这个模式的核心在于,它能让我们以…

作者头像 李华
网站建设 2026/5/15 10:28:59

Web Worker 与 SharedWorker 的区别:实现跨 Tab 页的 WebSocket 连接共享

各位技术同仁,大家好!今天我们将深入探讨Web Worker和SharedWorker这两种强大的Web API,并着重讲解它们在实现跨多个浏览器Tab页共享WebSocket连接这一复杂场景中的应用。在现代Web应用中,实时通信已成为标配,而WebSoc…

作者头像 李华
网站建设 2026/5/15 16:11:20

YashanDB数据库的跨平台迁移策略及实操经验

YashanDB 是一个相对较新的数据库,关于它的跨平台迁移策略和实操经验的文档和资料可能不如一些成熟的数据库系统丰富,但可以参考一些通用数据库迁移的策略和经验,以下是一些关键点:跨平台迁移策略1. 评估现有环境:- 确…

作者头像 李华
网站建设 2026/5/12 15:55:21

Http概述

文章目录Web基础-HTTP1、什么是项目2、什么是架构?3、架构所需关键词4、什么是集群?5、什么是负载均衡?6、http概述6.1、Web状态访问码6.2、Web的结构组成6.3、有哪些Web资源?6.4、HTTP的工作原理6.5、HTTP请求响应6.6、HTTP相关术…

作者头像 李华
网站建设 2026/5/9 19:23:54

线性系统(非线性系统)

线性系统(非线性系统) 若任意x(t)–系统–>y(t) ,则有ax(t)–系统–>ay(t)x1(t)–系统–>y1(t) x2(t)–系统–>y2(t) > x1(t) x2(t) --系统–> y1(t) y2(t)同时满足12 则是线性系统 齐次性 叠加性线性系统举例&#…

作者头像 李华