数据结构之链表操作详解与示例(反转链表,合并链表,旋转链表,对链表排序)

文章目录

    • 1. 反转链表
    • 2. 合并链表
    • 3. 旋转链表
    • 4. 对链表排序
    • 总结

在这里插入图片描述


链表是一种常见的基础数据结构,它在内存中的存储方式非常灵活。本文将详细介绍反转链表、合并链表、旋转链表以及对链表排序这四种操作,并提供C和C++的实现示例。

1. 反转链表

反转链表意味着我们需要改变链表中每个节点的指针方向。例如,给定一个链表 1 -> 2 -> 3 -> 4 -> 5,反转后变为 5 -> 4 -> 3 -> 2 -> 1。

算法步骤

  1. 初始化三个指针:prev(前一个节点)、curr(当前节点)和next(下一个节点)。
  2. 将prev初始化为None,curr初始化为链表的头节点,next初始化为None。
  3. 遍历链表,对于每个节点,执行以下操作:
    将next设置为curr的下一个节点。
    将curr的下一个节点设置为prev。
    将prev设置为curr。
    将curr设置为next。
  4. 最后,prev将是新的头节点,curr将是新的尾节点。

C++实现:

ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;while (curr != NULL) {ListNode* nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;
}

C实现:

ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;while (curr != NULL) {ListNode* nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;
}

2. 合并链表

合并链表意味着将两个或多个链表合并为一个有序链表。这里我们以合并两个升序链表为例。

算法步骤

  1. 初始化一个哨兵节点dummy,其下一个节点指向第一个链表的头节点。
  2. 使用两个指针分别遍历两个链表,比较当前两个链表的节点的值,将值较小的节点添加到dummy后面,并移动该指针到下一个节点。
  3. 当一个链表遍历完成后,将另一个链表的剩余部分直接连接到dummy后面。

C++实现:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}
}

C实现:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}
}

3. 旋转链表

旋转链表意味着将链表中的节点进行重新排列,例如,对于一个具有n个节点的链表,我们可以将链表的每个节点移动k个位置(k < n)。如果链表的最后一个节点需要移动到链表的头部,我们可以简单地将链表的头节点和尾节点连接起来。

算法步骤

  1. 计算链表中的元素个数n。
  2. 计算需要旋转的次数k(k可以是通过给定的步数或数组来确定)。
  3. 如果链表长度小于2,直接返回链表。
  4. 将链表的尾节点与头节点连接起来。
  5. 将新的头节点设置为当前尾节点的下一个节点。

C++实现:

ListNode* rotateRight(ListNode* head, int k) {if (head == NULL || head->next == NULL || k == 0) return head;ListNode* old_tail = head;int n;for (n = 1; old_tail->next != NULL; n++)old_tail = old_tail->next;old_tail->next = head; // 成环ListNode* new_tail = head;for (int i = 0; i < n - k % n - 1; i++)new_tail = new_tail->next;ListNode* new_head = new_tail->next;new_tail->next = NULL;return new_head;
}

C实现:

ListNode* rotateRight(ListNode* head, int k) {if (head == NULL || head->next == NULL || k == 0) return head;ListNode* old_tail = head;int n;for (n = 1; old_tail->next != NULL; n++)old_tail = old_tail->next;old_tail->next = head; // 成环ListNode* new_tail = head;for (int i = 0; i < n - k % n - 1; i++)new_tail = new_tail->next;ListNode* new_head = new_tail->next;new_tail->next = NULL;return new_head;
}

4. 对链表排序

对链表排序通常指的是对链表中的元素进行排序,以得到一个有序的链表。有多种方法可以实现链表排序,这里我们介绍两种常见的方法:归并排序和快速排序。

归并排序
归并排序是一种分治算法,它将链表分成两半,对每一半递归地进行排序,然后将排序好的两半合并起来。

C++实现:

ListNode* sortList(ListNode* head) {if (head == NULL || head->next == NULL) return head;ListNode* slow = head, *fast = head, *prev = NULL;while (fast != NULL && fast->next != NULL) {prev = slow;slow = slow->next;fast = fast->next->next;}prev->next = NULL; // 断开链表ListNode* l1 = sortList(head);ListNode* l2 = sortList(slow);return mergeTwoLists(l1, l2);
}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}
}

C实现:

ListNode* sortList(ListNode* head) {if (head == NULL || head->next == NULL) return head;ListNode* slow = head, *fast = head, *prev = NULL;while (fast != NULL && fast->next != NULL) {prev = slow;slow = slow->next;fast = fast->next->next;}prev->next = NULL; // 断开链表ListNode* l1 = sortList(head);ListNode* l2 = sortList(slow);return mergeTwoLists(l1, l2);
}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1;} else {l2->next = mergeTwoLists(l1, l2->next);return l2;}
}

总结

本文介绍了链表的四种常见操作:反转链表、合并链表、旋转链表和对链表排序。每种操作都有其特定的应用场景和算法步骤,通过示例代码展示了如何实现这些操作。理解和掌握这些链表操作对于深入理解数据结构和算法至关重要。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3246574.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

可以用EasyConnect连接实验室内网,但无法连接内网才能访问的服务器,为什么?

&#x1f3c6;本文收录于《CSDN问答解答》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&…

自动化产线 搭配数据采集监控平台 创新与突破

自动化产线在现在的各行各业中应用广泛&#xff0c;已经是现在的生产趋势&#xff0c;不同的自动化生产设备充斥在各行各业中&#xff0c;自动化的设备会产生很多的数据&#xff0c;这些数据如何更科学化的管理&#xff0c;更优质的利用&#xff0c;就需要数据采集监控平台来完…

昇思25天学习打卡营第04天|数据变换 Transforms

一、什么是数据变换 Transforms &#xff1f; 通常情况下&#xff0c;直接加载的原始数据并不能直接送入神经网络进行训练&#xff0c;此时我们需要对其进行数据预处理。MindSpore提供不同种类的数据变换&#xff08;Transforms&#xff09;&#xff0c;配合数据处理Pipeline来…

Docker存储目录问题,如何修改Docker默认存储位置?(Docker存储路径、Docker存储空间)etc/docker/daemon.json

文章目录 如何更改docker默认存储路径&#xff1f;版本1&#xff08;没测试&#xff09;版本2&#xff08;可行&#xff09;1. 停止 Docker 服务&#xff1a;2. 创建新的存储目录&#xff1a;3. 修改 Docker 配置文件&#xff1a;4. 移动现有的 Docker 数据&#xff1a;5. 重新…

电脑录屏win10可以用的软件有哪些?分享3款经典的!

在数字化时代&#xff0c;屏幕录制已成为我们工作、学习和娱乐中不可或缺的一部分。无论是教学演示、游戏直播还是软件操作教程&#xff0c;屏幕录制都能帮助我们轻松记录并分享屏幕上的精彩瞬间。那么&#xff0c;对于使用Win10系统的用户来说&#xff0c;有哪些值得推荐的屏幕…

可商用、性能超强!新开源Mamba架构纯代码模型

7月17日&#xff0c;法国著名开源大模型平台Mistral.ai在官网开源了&#xff0c;基于 Mamba架构的纯代码模型——Codestral Mamba。 根据测试数据显示&#xff0c;Codestral Mamba只有70亿参数&#xff0c;但性能却是Meta开源的知名代码模型CodeLlam 7B的两倍&#xff0c;成为…

Chromium源码阅读(9):了解事件跟踪TRACE_EVENT与第三方库Perfetto

Perfetto - System profiling, app tracing and trace analysis Perfetto 是一个用于性能检测和跟踪分析的生产级开源堆栈。它提供用于记录系统级和应用级跟踪的服务和库、本机 Java 堆分析、使用 SQL 分析跟踪的库以及用于可视化和探索多 GB 跟踪的基于 Web 的 UI。 See ht…

基础动态规划题目基础动态规划题目

目录 题目1&#xff1a; P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles 代码示例&#xff1a; 题目2&#xff1a; Common Subsequence 代码示例 题目3 &#xff1a;最长上升子序列 最长不下降子序列 最长上升子序列oj答案 题目1&#xff1a; P1216 [USACO1.5]…

【ffmpeg命令基础】过滤处理

文章目录 前言过滤处理的介绍两种过滤类型简单滤波图简单滤波图是什么简单滤波示例 复杂滤波图复杂滤波是什么区别示例 总结 前言 FFmpeg是一款功能强大的开源音视频处理工具&#xff0c;广泛应用于音视频的采集、编解码、转码、流化、过滤和播放等领域。1本文将重点介绍FFmpe…

软件确认测试报告包括的内容和作用简析,专业软件测试公司推荐

软件确认测试是指验证软件是否符合特定需求和规范的过程。它是软件开发生命周期中的一个关键环节&#xff0c;旨在确保软件的功能、性能、稳定性和安全性达到预期的标准&#xff0c;确认测试报告则是整个确认测试过程的总结和归纳&#xff0c;是对软件质量和稳定性的全面评估。…

5分钟教会你夸克网盘批量转存分享,夸克网盘批量保存,付详细图文

大家好&#xff0c;我是徐师兄&#xff0c;今天为大家带来的是夸克网盘批量转存分享&#xff0c;夸克网盘批量保存&#xff0c;付详细图文教程。 前言 夸克网盘批量保存工具下载 前段日子折腾夸克网盘的时候&#xff0c;找来了好多的资源&#xff0c;但这些资源链接非常多&a…

Transformer超详细解读

论文&#xff1a;Attention Is All You Need 作者&#xff1a;Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, Illia Polosukhin 机构&#xff1a;Google Brain 链接&#xff1a;https://arxiv.org/abs/1706.03762…

SQL Server Query Store Settings (查询存储设置)

参考&#xff1a;Query Store Settings - Erin Stellato 在 SQL Server 2017 中&#xff0c;有九 (9) 个设置与查询存储相关。虽然这些设置记录在sys.database_query_store_options中&#xff0c;但我经常被问到每个设置的值“应该”是多少。我在下面列出了每个设置&am…

EXCEL VBA工程密码破解 工作表保护破解

这里写目录标题 破解Excel宏工程加密方法一 新建破解宏文件方法二 修改二进制文件 破解工作表保护引用 破解Excel宏工程加密 如图所示 白料数据处理已工程被加密。 方法一 新建破解宏文件 1 创建一个XLSM文件&#xff0c;查看代码 ALTF11 2 新建一个模块&#xff0c;“插…

夏日狂欢水上漂流的爆笑奇遇记

【夏日狂欢&#xff0c;水上漂流的爆笑奇遇记 —— 月亮姐姐的“睫毛漂流记”】在这个炎炎夏日&#xff0c;当烈日炙烤着大地&#xff0c;每一寸空气弥漫着对清凉的渴望时&#xff0c;一场别开生面的“暑期嘉年华”正悄然掀起一场水上狂欢的浪潮。而在这场盛宴中&#xff0c;月…

【论文】(2024.6) KAN: Kolmogorov–Arnold Networks 阅读笔记 | KAN周边扩展

KAN的优势声称是能以更少的参数量实现更高的精度。KANs在数学上是可靠的、准确的和可解释的。 一 KAN 论文题目&#xff1a;KAN: Kolmogorov–Arnold Networks 论文地址&#xff1a;https://arxiv.org/pdf/2404.19756 代码地址&#xff1a;https://github.com/KindXiaoming/…

如何打造一个专属网盘?可道云teamOS这些个性化设置了解一下

在这个数字化时代&#xff0c;企业对于云端存储和协作工具的需求日益增长。而网盘作为企业协作的重要工具之一&#xff0c;其个性化、定制化的需求也日益凸显。 今天&#xff0c;我要为大家介绍的是一款高度个性化的企业网盘——可道云teamOS。 满足个性化需求的企业网盘 可…

防火墙NAT地址转换和智能选举综合实验

一、实验拓扑 目录 一、实验拓扑 二、实验要求&#xff08;接上一个实验要求后&#xff09; 三、实验步骤 3.1办公区设备可以通过电信链路和移动链路上网(多对多的NAT&#xff0c;并且需要保留一个公网IP不能用来转换) 3.2分公司设备可以通过总公司的移动链路和电信链路访…

【深度学习】PyTorch框架(4):初始网络、残差网络 和密集连接网络

1、引言 在本篇文章中&#xff0c;我们将深入探讨并实现一些现代卷积神经网络&#xff08;CNN&#xff09;架构的变体。近年来&#xff0c;学界提出了众多新颖的网络架构。其中一些最具影响力&#xff0c;并且至今仍然具有重要地位的架构包括&#xff1a;GoogleNet/Inception架…

Qt Style Sheets-使用样式表自定义 Qt 部件

使用样式表自定义 Qt 部件 在使用样式表时&#xff0c;每个小部件都被视为具有四个同心矩形的框&#xff1a;边距矩形、边框矩形、填充矩形和内容矩形。框模型对此进行了更详细的描述。 盒模型 以下是四个同心矩形在概念上的呈现方式&#xff1a; 边距超出边框。边框绘制在边…