数据结构——重排链表(经典题目,涉及三个知识点)

ops/2024/11/19 12:28:06/

一、示例
在这里插入图片描述

在这里插入图片描述

二、上代码

class Solution {
public:void reorderList(ListNode* head) {if (head == nullptr || head->next == nullptr) return;ListNode* mid = FindMiddleNode(head);   // 找到中间节点ListNode* l1 = head;ListNode* l2 = mid->next;mid->next = nullptr;l2 = ReverseList(l2);   // 反转后半段的链表节点mergeList(l1, l2);      // 合并两端长度相差不超过1的链表}// 快慢指针找到中间节点ListNode* FindMiddleNode(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast->next != nullptr && fast->next->next != nullptr) {slow = slow->next;fast = fast->next->next;}return slow;}// 反转链表ListNode* ReverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* cur = head;ListNode* next;while (cur != nullptr) {next = cur->next;cur->next = pre; // 反转pre = cur;       // 向后移动cur = next;}return pre;}// 合并链表void mergeList(ListNode* l1, ListNode* l2) {ListNode* temp1;ListNode* temp2;while (l1 != nullptr && l2 != nullptr) {temp1 = l1->next;temp2 = l2->next;l1->next = l2;l1 = temp1;l2->next = l1;l2 = temp2;}}
};

三、详解

算法思想:将链表分成两半来处理,前半部分,和后半部分;针对后半部分进行逆序,再从前半部分和逆序后的后半部分分别取一个结点组成一个新的链表。然后就将上面问题分解成更细粒度的子问题:

1、寻找中间节点 FindMiddleNode,采用了快慢指针的算法。

2、链表逆序参考前面文章:链表逆序
本文采用的正向遍历,前面文章采用的递归,都要掌握。

3、合并前半段链表和后半段链表


http://www.ppmy.cn/ops/134969.html

相关文章

shell中的case语句和循环语句

文章目录 🍊自我介绍🍊shell中的case语句匹配常量匹配变量匹配字符串列表 🍊循环语句while 循环for 循环单词表通过逐个列出单词通过变量中的数据通过命令行传输单词表 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点…

基于单片机的风能太阳能供电的路灯智能控制系统设计(论文+源码)

1系统总体设计 本课题为风能太阳能供电的路灯智能控制系统设计,系统的主要功能设计如下: (1) 供电模块:采用太阳能板以及风机模拟风扇充电,经过充电电路给锂电池进行充电。再由锂电池给照明模块以及整个项…

pxe自动装机(centos)

概述 PXE(Preboot Execution Environment)是一种允许计算机通过网络启动自己的操作系统的技术。它允许计算机在缺少本地存储设备或操作系统的情况下,从远程服务器上下载并执行操作系统。PXE通常用于无盘站点或远程支持,可以通过网…

Java进阶(JVM)

Java进阶(一) 一. JVM 1.1 为什么学习JVM 首先面试需要 高级程序员也更需要了解JVM 1.2 JVM作用 JVM负责把编译后的字节转换为机器码 1.3 JVM内部构造 1.3.1 类加载部分: 负责把硬盘上字节码加载到内存中(运行时数据区) 1.3.2 运行时数据区: …

RN开发搬砖经验之—React Native(RN)应用转原生化-Android 平台

在过去的一年中,我的主要工作聚焦于将一个基于React Native(RN)框架开发的Android应用逐步转化为原生应用。我们采取了分阶段实施的策略,首先着手将应用中的二级和三级页面的核心功能以原生代码的形式进行重构。在这一过程中&…

鸿蒙next版开发:相机开发-元数据(ArkTS)

在HarmonyOS 5.0中,ArkTS提供了对相机元数据的访问能力,这对于开发者在相机应用中获取图像的详细信息非常有用。元数据(Metadata)是对相机返回的图像信息数据的描述和上下文,比如照片或视频中识别人像的取景框坐标等信…

Spring Boot汽车资讯:科技与速度的新纪元

摘要 随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了汽车资讯网站的开发全过程。通过分析汽车资讯网站管理的不足,创建了一个计算机管理汽车资讯网站的方案。文章介绍了汽车资讯网站的系统分析部分&…

缓存及其不一致

在实际开发过程中,一般都会遇到缓存,像本地缓存(直接在程序里搞个map也可以,但是可能会随着数据的增长出现OOM,建议使用正经的本地缓存框架,因为自己实现淘汰策略啥的挺费劲的)、分布式缓存&…