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

文章目录

    • 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://www.rhkb.cn/news/376901.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【数学建模】——【线性规划】及其在资源优化中的应用

目录 线性规划问题的两类主要应用&#xff1a; 线性规划的数学模型的三要素&#xff1a; 线性规划的一般步骤&#xff1a; 例1&#xff1a; 人数选择 例2 &#xff1a;任务分配问题 例3: 饮食问题 线性规划模型 线性规划的模型一般可表示为 线性规划的模型标准型&…

AI大模型探索之旅:深潜大语言模型的训练秘境

在人工智能的浩瀚星空中&#xff0c;大语言模型无疑是最耀眼的星辰之一&#xff0c;它们以无与伦比的语言理解与生成能力&#xff0c;引领着智能交互的新纪元。本文将带您踏上一场探索之旅&#xff0c;深入大语言模型的训练秘境&#xff0c;揭开其背后复杂而精妙的全景画卷。 …

免杀笔记 ----> 动态调用

前一段时间不是说要进行IAT表的隐藏吗&#xff0c;终于给我逮到时间来写了&#xff0c;今天就来先将最简单的一种方式 ----> 动态调用&#xff01;&#xff01;&#xff01; 1.静态查杀 这里还是说一下我们为什么要对他进行隐藏呢&#xff1f;&#xff1f;&#xff1…

CAN总线学习

can主要用于汽车、航空等控制行业&#xff0c;是一种串行异步通信方式&#xff0c;因为其相较于其他通信方式抗干扰能力更强&#xff0c;更加稳定。原因在于CAN不像其他通信方式那样&#xff0c;以高电平代表1&#xff0c;以低电平代表0&#xff0c;而是通过电压差来表示逻辑10…

STM32MP135裸机编程:唯一ID(UID)、设备标识号、设备版本

0 资料准备 1.STM32MP13xx参考手册1 唯一ID&#xff08;UID&#xff09;、设备标识号、设备版本 1.1 寄存器说明 &#xff08;1&#xff09;唯一ID 唯一ID可以用于生成USB序列号或者为其它应用所使用&#xff08;例如程序加密&#xff09;。 &#xff08;2&#xff09;设备…

使用Python和MediaPipe实现手势虚拟鼠标控制

概述 使用Python实现虚拟鼠标控制&#xff0c;利用手势识别来替代传统鼠标操作。这一实现依赖于计算机视觉库OpenCV、手势识别库MediaPipe以及其他辅助库如PyAutoGUI和Pynput。 环境配置 在开始之前&#xff0c;请确保已安装以下Python库&#xff1a; pip install opencv-p…

SadTalker数字人服务器部署

一、单独SadTalker部署 git clone https://github.com/OpenTalker/SadTalker.gitcd SadTalker conda create -n sadtalker python3.8conda activate sadtalkerpip install torch1.12.1cu113 torchvision0.13.1cu113 torchaudio0.12.1 --extra-index-url https://download.pyto…

RuoYi-后端管理项目入门篇1

目录 前提准备 下载若依前后端 Gitee 地址 准备环境 后端数据库导入 1 克隆完成 若依后端管理后端 Gitte 地址 :若依/RuoYi-Vue 2.1 创建Data Source数据源 2.2 填写好对应的数据库User 和 Password 点击Apply 2.3 新建一个Schema 2.4 填写对应数据库名称 这边演示写的…

husky 和 lint-staged 构建代码项目规范

目录 前言 最简单的方法 过 scripts 来解决如果检测工具多&#xff0c;需要多次处理 通过 husky(哈士奇)来解决容易遗忘的问题 1. 安装 2. husky init 3. 试一试​ lint-stadge 只 lint 改动的 1. 安装 2. 修改 package.json 配置 3. 添加 npm 脚本: 4.使用 Husky…

缓存与分布式锁

一、缓存 1、缓存使用 为了系统性能的提升&#xff0c;我们一般都会将部分数据放入缓存中&#xff0c;加速访问。 适合放入缓存的数据有&#xff1a; 即时性、数据一致性要求不高的&#xff1b;访问量大且更新频率不高的数据。 在开发中&#xff0c;凡是放入缓存中的数据我们都…

语言主要是一种交流工具,而不是思维工具?GPT5何去何从?

引言 在人工智能领域&#xff0c;特别是大语言模型&#xff08;LLM&#xff09;的发展中&#xff0c;语言和思维的关系一直是一个备受关注的话题。近期&#xff0c;麻省理工学院&#xff08;MIT&#xff09;在《Nature》杂志上发表了一篇题为《Language is primarily a tool f…

【ChatGPT】深入解析Prompt提示词及如何高效使用ChatGPT

一、Prompt提示词是什么&#xff1f; 1.1 Prompt的定义 Prompt是人工智能领域中的一个关键概念&#xff0c;尤其在自然语言处理&#xff08;NLP&#xff09;和生成型AI模型中。简而言之&#xff0c;prompt是一段文本或指令&#xff0c;用于引导或启动AI模型的特定响应或操作。…

Linux - 基础开发工具(yum、vim、gcc、g++、make/Makefile、git)

目录 Linux软件包管理器 - yum Linux下安装软件的方式 认识yum 查找软件包 安装软件 如何实现本地机器和云服务器之间的文件互传 卸载软件 Linux编辑器 - vim vim的基本概念 vim下各模式的切换 vim命令模式各命令汇总 vim底行模式各命令汇总 vim的简单配置 Linux编译器 - gc…

Spring-Cache 缓存

1.简介 2.SpringCache 整合 简化缓存开发 1.导入依赖 <!-- spring cache --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-cache</artifactId></dependency>2.redis 作为缓存…

Mac应用程序清理卸载工具:App Cleaner Uninstaller for Mac 中文版

App Cleaner Pro是一款Mac上非常好用的软件卸载工具&#xff0c;支持应用卸载、Widget卸载、浏览器插件卸载&#xff0c;支持拖拽卸载和列表卸载&#xff0c;能够非常干净的卸载应用&#xff0c;节省你的磁盘空间。App Cleaner Uninstaller Pro是一款深度清理和卸载的工具&…

什么是边缘计算?创造一个更快、更智慧、更互联的世界

前言 如今&#xff0c;数十亿物联网传感器广泛部署在零售商店、城市街道、仓库和医院等各种场所&#xff0c;正在生成大量数据。从这些数据中更快地获得洞察&#xff0c;意味着可以改善服务、简化运营&#xff0c;甚至挽救生命。但要做到这一点&#xff0c;企业需要实时做出决策…

Excel第30享:基于辅助列的条件求和

1、需求描述 如下图所示&#xff0c;现要统计2022年YTD&#xff08;Year To Date&#xff1a;年初至今日&#xff09;各个人员的“上班工时&#xff08;a2&#xff09;”。 下图为系统直接导出的工时数据明细样例。 2、解决思路 Step1&#xff1a;确定逻辑。“从日期中提取出…

virtualbox的ubuntu默认ipv4地址为10.0.2.15的修改以及xshell和xftp的连接

virtualbox安装Ubuntu后&#xff0c;默认的地址为10.0.2.15 我们查看virtualbox的设置发现是NAT 学过计算机网络的应该了解NAT技术&#xff0c;为了安全以及缓解ip使用&#xff0c;我们留了部分私有ip地址。 私有IP地址网段如下&#xff1a; A类&#xff1a;1个A类网段&…

jenkins系列-09.jpom构建java docker harbor

本地先启动jpom server agent: /Users/jelex/Documents/work/jpom-2.10.40/server-2.10.40-release/bin jelexjelexxudeMacBook-Pro bin % sh Server.sh start/Users/jelex/Documents/work/jpom-2.10.40/agent-2.10.40-release/bin jelexjelexxudeMacBook-Pro bin % ./Agent.…

SAP PP学习笔记26 - User Status(用户状态)的实例,订单分割中的重要概念 成本收集器,Confirmation(报工)的概述

上面两章讲了生产订单的创建以及生产订单的相关内容。 SAP PP学习笔记24 - 生产订单&#xff08;制造指图&#xff09;的创建_sap 工程外注-CSDN博客 SAP PP学习笔记25 - 生产订单的状态管理(System Status(系统状态)/User Status(用户状态)),物料的可用性检查&#xff0c;生…