算法: 链表题目练习

文章目录

  • 链表题目练习
    • 两数相加
    • 两两交换链表中的节点
    • 重排链表
    • 合并 K 个升序链表
    • K 个一组翻转链表
  • 总结

链表题目练习

两数相加

在这里插入图片描述
坑:

  • 两个链表都遍历完后,可能需要进位.
    class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 = l1;ListNode cur2 = l2;ListNode head = new ListNode(0);ListNode tail = head;int sum = 0;while (cur1 != null || cur2 != null) {ListNode newNode = new ListNode();tail.next = newNode;tail = newNode;if (cur1 != null) {sum += cur1.val;cur1 = cur1.next;}if (cur2 != null) {sum += cur2.val;cur2 = cur2.next;}if (sum >= 10) {newNode.val = sum % 10;sum = 1;} else {newNode.val = sum;sum = 0;}}// 遍历完两个链表 处理一下进位if (sum != 0) {ListNode newNode = new ListNode(sum);tail.next = newNode;}return head.next;}}

题解代码:

    class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 = l1, cur2 = l2;ListNode head = new ListNode();ListNode tail = head;int sum = 0;while (cur1 != null || cur2 != null || sum != 0) {if (cur1 != null) {sum += cur1.val;cur1 = cur1.next;}if (cur2 != null) {sum += cur2.val;cur2 = cur2.next;}ListNode newNode = new ListNode(sum % 10);tail.next = newNode;tail = newNode;sum /= 10;}return head.next;}}

两两交换链表中的节点

在这里插入图片描述
简简单单,一遍过~

草图 :
在这里插入图片描述

    class Solution {public ListNode swapPairs(ListNode head) {ListNode virtualHead = new ListNode();virtualHead.next = head;ListNode cur = head, prev = virtualHead;while (cur != null && cur.next != null) {ListNode next = cur.next;prev.next = next;cur.next = next.next;next.next = cur;prev = cur;cur = cur.next;}return virtualHead.next;}}

重排链表

在这里插入图片描述
没想出来,看题解思路懂哩~

分成三步走：

  1. 找到原链表的中间节点（可以使用快慢指针解决）。
  2. 将原链表的右半部分翻转。
  3. 将原链表的两端合并。
    • 因为两链表的长度相差不超过 1，所以可以直接合并~

磕磕绊绊总算是写出来了~
看似是一道题，其实是三道题~

在合并两个链表时卡了一下.

坑:

  • 前面有指针指向 中间节点 ,链表翻转后指针的指向大概是这样的
    在这里插入图片描述
class Solution {public void reorderList(ListNode head) {// 寻找中间节点ListNode fast = head, slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// 此时 slow 为中间节点// 翻转 slow 以及 slow 后面的节点ListNode behind = new ListNode();ListNode cur = slow;while (cur != null) {ListNode next = cur.next;cur.next = behind.next;behind.next = cur;cur = next;}// 合并两个链表ListNode cur1 = head, cur2 = behind.next;while (cur2.next != null && cur1.next != null) {ListNode next1 = cur1.next, next2 = cur2.next;cur2.next = next1;cur1.next = cur2;cur1 = next1;cur2 = next2;}}
}

看了题解之后,发现可以把整个链表拆成两份.
而且,发现从中间节点的后一个开始翻转链表也可以过,这样就可以在中间节点这个位置把链表分成两份:

  • 一份是 中间节点之前(包含中间节点)
  • 另一份是 中间节点之后

题解代码:

    class Solution {public void reorderList(ListNode head) {// 1.寻找中间节点ListNode slow = head, fast = slow;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode head2 = new ListNode(-1);// 2.逆序 head2 链表ListNode cur = slow.next;// 拆分成两个链表slow.next = null;while (cur != null) {ListNode next = cur.next;cur.next = head2.next;head2.next = cur;cur = next;}// 3. 合并两个链表ListNode head3 = new ListNode(-1);ListNode cur2 = head;ListNode cur3 = head2.next;ListNode prev = head3;while (cur2 != null) {prev.next = cur2;prev = cur2;cur2 = cur2.next;if (cur3 != null) {prev.next = cur3;prev = cur3;cur3 = cur3.next;}}}}

合并 K 个升序链表

在这里插入图片描述
解法一: 不断合并两个链表

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {private ListNode mergeLists(ListNode l1, ListNode l2) {if (l1 == null)return l2;if (l2 == null)return l1;ListNode head = new ListNode(-1);ListNode cur1 = l1, cur2 = l2, tail = head;while (cur1 != null && cur2 != null) {if (cur1.val <= cur2.val) {tail.next = cur1;tail = cur1;cur1 = cur1.next;} else {tail.next = cur2;tail = cur2;cur2 = cur2.next;}}while (cur1 != null) {tail.next = cur1;tail = cur1;cur1 = cur1.next;}while (cur2 != null) {tail.next = cur2;tail = cur2;cur2 = cur2.next;}return head.next;}public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n <= 0)return null;ListNode head = lists[0];for (int i = 1; i < n; i++) {head = mergeLists(head, lists[i]);}return head;}
}

方法二: 使用优先级队列优化.

  • 给每个链表都指定一个指针(用来遍历链表),把每一个指针指向的节点放到优先级队列里.不断取出值最小的那个节点,尾插到结果链表中.

忘了怎么在java中自定义排序优先级队列了。

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n == 0)return null;// 指针数组ListNode[] arr = new ListNode[n];// 默认是小根堆PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {@Overridepublic int compare(ListNode o1, ListNode o2) {return o1.val - o2.val;}});// 结果ListNode ret = new ListNode(-1);ListNode tail = ret;// 把指针对应起来for (int i = 0; i < n; i++) {arr[i] = lists[i];}for (int i = 0; i < n; i++) {if (arr[i] != null) {heap.add(arr[i]);}}while (!heap.isEmpty()) {// 最小的出堆ListNode min = heap.poll();// 拼到结果后面tail.next = min;tail = tail.next;if (min.next != null) {// 不为空，入堆heap.add(min.next);}}return ret.next;}
}

看了题解代码后，发现自己写的代码浪费了很多空间，我为什么要 new 一个指针数组？？？

题解代码：

        /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n == 0)return null;// 1. 创建一个小根堆PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);// 2. 把所有的头结点放进小根堆中for (ListNode head : lists) {if (head != null)heap.offer(head);}// 3.合并链表ListNode ret = new ListNode(-1);ListNode tail = ret;while (!heap.isEmpty()) {// 最小的出堆ListNode min = heap.poll();// 拼到结果后面tail.next = min;tail = tail.next;if (min.next != null) {// 不为空，入堆heap.add(min.next);}}return ret.next;}}

方法三：使用 分治 - 递归 解决

好难想到。

代码：

        /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {// 合并两个有序链表public ListNode mergeLists(ListNode l1, ListNode l2) {if (l1 == null)return l2;if (l2 == null)return l1;ListNode head = new ListNode(-1);ListNode tail = head;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {tail.next = l1;l1 = l1.next;} else {tail.next = l2;l2 = l2.next;}tail = tail.next;}while (l1 != null) {tail.next = l1;l1 = l1.next;tail = tail.next;}while (l2 != null) {tail.next = l2;l2 = l2.next;tail = tail.next;}return head.next;}// 递归public ListNode merge(ListNode[] lists, int start, int end) {if (start >= end)return lists[start];int mid = start + (end - start) / 2;ListNode l1 = merge(lists, start, mid);ListNode l2 = merge(lists, mid + 1, end);return mergeLists(l1, l2);}public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n == 0)return null;return merge(lists, 0, n - 1);}}

自己的代码中的合并两个有序链表的代码写的不是很好，最后的 while 可以换成 if 来写的，这是链表，不是数组，不用循环那么多次。。

题解代码：

        /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {// 合并两个有序链表public ListNode mergeLists(ListNode l1, ListNode l2) {if (l1 == null)return l2;if (l2 == null)return l1;ListNode head = new ListNode(-1);ListNode tail = head;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {tail.next = l1;l1 = l1.next;} else {tail.next = l2;l2 = l2.next;}tail = tail.next;}if (l1 != null)tail.next = l1;if (l2 != null)tail.next = l2;return head.next;}// 递归public ListNode merge(ListNode[] lists, int start, int end) {if (start >= end)return lists[start];// 1. 平分数组int mid = start + (end - start) / 2;// 2. 递归处理左右两个部分ListNode l1 = merge(lists, start, mid);ListNode l2 = merge(lists, mid + 1, end);// 3. 合并两个有序链表return mergeLists(l1, l2);}public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n == 0)return null;return merge(lists, 0, n - 1);}}

K 个一组翻转链表

在这里插入图片描述

自己写的代码：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverse(ListNode head, int k) {ListNode phead = new ListNode(-1);ListNode cur = head, next = cur.next;while (k-- > 0) {cur.next = phead.next;phead.next = cur;cur = next;if (next != null)next = next.next;elsebreak;}return phead.next;}public ListNode reverseKGroup(ListNode head, int k) {ListNode phead = new ListNode(-1);phead.next = head;ListNode slow = phead, fast = head;while (fast != null) {int tmp = k;while (tmp > 0) {if (fast == null) {break;}fast = fast.next;tmp--;}if (tmp > 0)break;slow.next = reverse(slow.next, k);tmp = k;// 写成这样你要清楚：// 等出循环的时候 tmp = -1// 因为在最后一次的判断时 tmp 也要 --while (tmp-- > 0) {slow = slow.next;}slow.next = fast;}return phead.next;}
}

题解代码：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 1. 先求出要逆序多少组int n = 0;ListNode cur = head;while (cur != null) {cur = cur.next;n++;}n /= k;// 2. 重复 n 次，长度为 k 的链表的逆序ListNode newHead = new ListNode(-1);ListNode prev = newHead;cur = head;for (int i = 0; i < n; i++) {// 标记当前逆序后的最后一个节点ListNode tmp = cur;for (int j = 0; j < k; j++) {ListNode next = cur.next;cur.next = prev.next;prev.next = cur;cur = next;}prev = tmp;}// 处理剩下的节点不够 k 个的情况prev.next = cur;return newHead.next;}
}

总结

链表常用技巧 :

  1. 画图是个好东西（感觉好像已经说过好几遍了）.
  2. 可以引入一个头结点
    • 便于处理边界情况
    • 方便我们对链表操作
  3. 在插入新节点时,可以先把新节点的指针指向都调整好.然后再去调整前一个节点和后一个节点.
    或者直接新建一个指针,指向后一个节点,这样更容易操作~
  4. 有时候会用到快慢双指针

本文到这里就结束啦~

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

交替传译收费标准

交替传译收费标准

交替传译是一种高端口服务&#xff0c;常用于国际会议、商务洽谈、学术交流等多语言会议场合&#xff0c;演讲者的发言一般不超过15分钟&#xff0c;交替传译员和演讲者采取接力式交替发言&#xff0c;在这种模式下&#xff0c;口译员需要具备优秀的记忆能力和翻译功底。其价格…
阅读更多...
灵动AI视频：重塑视频创作，智启无限灵感！

灵动AI视频：重塑视频创作，智启无限灵感！

&#x1f680; 在这个视觉为王的时代&#xff0c;视频创作已成为展现创意与才华的重要舞台。然而&#xff0c;繁琐的剪辑流程、有限的创意资源往往成为制约创作者发挥的瓶颈。灵动AI视频&#xff0c;一款集智能、高效、创意于一体的视频编辑神器&#xff0c;正为视频创作领域带…
阅读更多...
生物信息学R语言

生物信息学R语言

检查R语言安装包和依赖 .libPaths() 这里有一个简单的生物信息学分析案例&#xff0c;使用R语言处理基因表达数据。这个示例中&#xff0c;我们将导入模拟的基因表达数据&#xff0c;进行数据预处理&#xff08;如归一化&#xff09;&#xff0c;并使用主成分分析&#xff08…
阅读更多...
基于VsCode platformio的stm32开发环境搭建

基于VsCode platformio的stm32开发环境搭建

背景 VsCode作为当下流行的编辑器&#xff0c;且不单单是一个编辑器里面集成了很多插件&#xff0c;使用这些插件可以完成很多功能。 STM32开发环境除了KEIL与IAR&#xff0c;其实还有很多其他的开方方式&#xff0c;ST官方提供了很多的开发软件&#xff0c;基于Eclipse也可以…
阅读更多...
【题解】【排序】—— [NOIP2017 普及组] 图书管理员

【题解】【排序】—— [NOIP2017 普及组] 图书管理员

【题解】【排序】—— [NOIP2017 普及组] 图书管理员 [NOIP2017 普及组] 图书管理员题目背景题目描述输入格式输出格式输入输出样例输入 #1输出 #1 提示 1.思路解析2.AC代码 [NOIP2017 普及组] 图书管理员 通往洛谷的传送门 题目背景 NOIP2017 普及组 T2 题目描述 图书馆中…
阅读更多...
华为和思科的配置

华为和思科的配置

vrrp和mstp 思路 vrrp是用来虚拟网关&#xff0c;噢&#xff0c;是虚拟一条虚拟网关 优先级&#xff0c;priority越大越优先&#xff0c;优先级相同&#xff0c;哪个的路由器的vrrp先起来&#xff0c;谁就是主 mstp是快速生成树协议&#xff0c;防止环路用的 优先级越小越优…
阅读更多...
React 前端如何通过组件完成 “下载 Excel模板” 和 “上传 Excel 文件并读取内容生成可使用的对象数组”

React 前端如何通过组件完成 “下载 Excel模板” 和 “上传 Excel 文件并读取内容生成可使用的对象数组”

文章目录 一、Excel 模板下载01、代码示例 二、Excel 文件上传01、文件展示02、示例代码03、前端样式展示04、数据结果展示 三、完整代码 本文的业务需求是建立在批量导入数据的情况下&#xff0c;普通组件只能少量导入&#xff0c;数据较多的情况都会选择 Excel 数据导入&…
阅读更多...
『统计检验』一篇文章入门置信区间

『统计检验』一篇文章入门置信区间

文章目录 置信区间点估计和区间估计置信度置信区间的计算置信区间计算的具体例子 参考文献 置信区间 置信区间是总体参数落在测量结果周围的程度 点估计和区间估计 点估计&#xff1a;通过样本数据估计总体参数 ⇒ \Rightarrow ⇒使用样本统计量&#xff08;如样本均值、样本…
阅读更多...
ESRALLY安装与使用

ESRALLY安装与使用

ESRALLY安装与使用 geonames、geopoint：都是和地理位置相关的，如果需要测试ES在地理位置处理的性能可以选用 http_logs：是http_server的，如果要测服务器日志、redis日志、apache日志可以选用 说明：esrally 自带的测试数据即为 rally_track 文件夹中的内容，主要包括: Ge…
阅读更多...
SpringMvc day1101

SpringMvc day1101

ok了家人们&#xff0c;今天我们继续 studying springMvc&#xff0c;let‘me see see 四.SSM整合 SpringMVC Spring MyBatis WebConfig SpringConfigMybatisConfig SpringMvcSupport jdbc.properties 表现层 业务层持久层 EmpController EmpServiceEmpMapper EmpServiceIm…
阅读更多...
关于基于 GA102 核心的显卡及主要参数

关于基于 GA102 核心的显卡及主要参数

基于 GA102 核心的显卡的主要参数&#xff1a; 主要用途 高端游戏, 专业图形处理 高端游戏, 专业图形处理 高端游戏, 专业图形处理 高端游戏, 专业图形处理 专业图形处理, 数据中心 数据中心, AI 计算 解释 CUDA 核心数&#xff1a;更多的 CUDA 核心意味着更强的并行计算能力。…
阅读更多...
C++ 多态 （详解）

C++ 多态 （详解）

多态的概念 通俗来说&#xff0c;就是多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当不同的对象去完成时会产生出不同的状态。举个栗子&#xff1a;比如买票这个行为&#xff0c;当普通人买票时&#xff0c;是全价买票&#xff1b;学生买票时&#xff0c;是半价…
阅读更多...
雷池社区版新版本功能防绕过人机验证解析

雷池社区版新版本功能防绕过人机验证解析

前两天&#xff0c;2024.10.31&#xff0c;雷池社区版更新7.1版本&#xff0c;其中有一个功能&#xff0c;新增请求防重放 更新记录&#xff1a;hhttps://docs.waf-ce.chaitin.cn/zh/%E7%89%88%E6%9C%AC%E6%9B%B4%E6%96%B0%E8%AE%B0%E5%BD%95 仔细研究了这个需求&#xff0c;…
阅读更多...
省级-社会保障水平数据（2007-2022年）

省级-社会保障水平数据（2007-2022年）

社会保障水平是一个综合性的概念&#xff0c;它不仅涉及到一个国家或地区的社会保障制度覆盖范围&#xff0c;还包括了提供的保障种类与水平&#xff0c;以及这些制度在满足公民基本生活需求方面的能力。 2007-2022年省级-社会保障水平数据.zip资源-CSDN文库https://download.…
阅读更多...
如何搭建汽车行业AI知识库：定义+好处+方法步骤

如何搭建汽车行业AI知识库：定义+好处+方法步骤

在汽车行业&#xff0c;大型车企面临着员工众多、价值链长、技术密集和知识传播难等挑战。如何通过有效的知识沉淀与应用&#xff0c;提升各部门协同效率&#xff0c;快速响应客户咨询&#xff0c;降低销售成本&#xff0c;并开启体系化、可持续性的知识管理建设&#xff0c;成…
阅读更多...
【C++篇】数据之林：解读二叉搜索树的优雅结构与运算哲学

【C++篇】数据之林：解读二叉搜索树的优雅结构与运算哲学

文章目录 二叉搜索树详解&#xff1a;基础与基本操作前言第一章&#xff1a;二叉搜索树的概念1.1 二叉搜索树的定义1.1.1 为什么使用二叉搜索树&#xff1f; 第二章&#xff1a;二叉搜索树的性能分析2.1 最佳与最差情况2.1.1 最佳情况2.1.2 最差情况 2.2 平衡树的优势 第三章&a…
阅读更多...
如何在Linux下部署自己的ZFile开源网盘

如何在Linux下部署自己的ZFile开源网盘

ZFile 项目介绍 ZFile是一个功能强大、灵活的开源网盘系统&#xff0c;为用户提供安全便捷的文件存储和共享方案。 项目概述 ZFile由ZFile, Inc.开发和维护&#xff0c;基于Docusaurus构建。其用户友好的界面支持多种文件存储和共享功能&#xff0c;并具备高度的可定制性和扩…
阅读更多...
平替、超越Jira？18 个最佳 Jira 替代方案【开源+免费+付费】

平替、超越Jira？18 个最佳 Jira 替代方案【开源+免费+付费】

Jira 是一种流行的项目管理工具&#xff0c;被团队广泛用于跟踪和管理他们的任务、问题和项目。 打个不太恰当的比喻&#xff0c;Jira &#xff0c;她就是项目管理家的单反。 如果您正在寻找 Jira 的替代方案&#xff0c;本文介绍了 18个最重要的 Jira 替代方案&#xff0c;可以…
阅读更多...
Nuxt.js 应用中的 nitro：build：public-assets 事件钩子详解

Nuxt.js 应用中的 nitro：build：public-assets 事件钩子详解

title: Nuxt.js 应用中的 nitro：build：public-assets 事件钩子详解 date: 2024/11/5 updated: 2024/11/5 author: cmdragon excerpt: nitro:build:public-assets 是 Nuxt 3 中的一个生命周期钩子，在复制公共资产之后调用。该钩子使开发者能够在构建 Nitro 服务器之前，对…
阅读更多...
02_CC2530 + LED流水灯

02_CC2530 + LED流水灯

CC2530 LED流水灯 前言 ​ 在搭建ZigBee定位系统前&#xff0c;先通过几个基础案例熟悉CC2530的一些外设和寄存器编程方式。CC2530基础篇由LED流水灯(按键控制启停、定时器中断方式)、定时器与Delay_ms延时函数、Uart串口通信三章组成。 按键控制启停–通用I/O中断 硬件电…
阅读更多...
最新文章

Copyright @ 2022~2023