您现在的位置是:首页 > Javascript
当前栏目
实现链表反转,你学会了吗?
2023-02-25 18:03:01 时间
前言
有一个链表,如何将其反转并获取反转后的链表头节点?本文将分享一种解决方案,欢迎各位感兴趣的开发者阅读本文。
思路分析
经过数据结构基础的学习,我们知道链表中每个节点都会有一个指针,用于指向它的下一个节点,那么,我们只需要从链表头部开始遍历,逐一修改它的指针指向至其上一个节点,即可完成链表的反转。
这个思路的难点在于如何调整指针的指向,我们可以借助3个指针来完成这个操作,如下所示:
- p1、p3分别是p2指针的上、下一个节点(默认指向null)
- 如果p2指针指向的节点不为null
获取p2指针指向的下一个节点,将其保存至p3
如果p3的值为null,则表示链表已经反转完毕,用一个变量存储p2的值
修改p2指针的指向至p1,修改p1的值为p2,修改p2的值为p3
实现代码
通过上面的分析,我们分析出了可以用三指针来解决问题的思路,接下来,我们来看下代码实现。
首先,设计一个名为ReverseLinkedList的类:
- 内部有2个私有变量。
pPrev p1指针
pNode p2指针
- 构造方法接受1个参数:链表头节点。
对参数进行校验。
初始化p2指针指向为链表头节点,p1指针的指向为null。
export class ReverseLinkedList {
// p1指针
private pPrev: ListNode | null;
// p2指针
private pNode: ListNode | null;
constructor(listHead: ListNode) {
if (listHead == null) {
throw new Error("链表头节点不能为空");
}
this.pNode = listHead;
this.pPrev = null;
}
}
上述代码中,我们用了一个自定义类型ListNode,它描述了一个链表的节点应该包含哪些属性,对此感兴趣的开发者请移步我的另一篇文章:链表与变相链表的实现。
紧接着,实现链表反转函数:
- 声明一个变量用于存储反转后的链表头指针。
- 移动p2指针,开始遍历链表。
存储p2指针的下一个节点至p3。
判断p2指针是否为走到链表末尾,条件成立就修改存储p2节点至反转后的链表头指针变量。
修改p2指针的指向至p1,修改p1的值为p2,修改p2的值为p3。
- p2指针指向null,返回得到的链表头节点。
reverseList(): ListNode | null {
// 反转后的链表头指针
let pReversedHead: ListNode | null = null;
while (this.pNode != null) {
// p3指针
const pNext = this.pNode.next;
if (pNext == null) {
pReversedHead = this.pNode;
}
this.pNode.next = this.pPrev;
this.pPrev = this.pNode;
this.pNode = pNext;
}
return pReversedHead;
}
完整代码请移步:ReverseLinkedList.ts
测试用例
接下来,我们将前言中的例子代入上个章节所实现的函数中,验证下它能否得出正确的结果。
const linkedList = new LinkedList();
linkedList.push(1);
linkedList.push(3);
linkedList.push(8);
linkedList.push(9);
linkedList.push(12);
linkedList.push(18);
const reverseLinkedList = new ReverseLinkedList(linkedList.getHead());
const result = reverseLinkedList.reverseList();
console.log("反转后的链表头节点为", result);
运行结果如下所示,成功的解决了文章前言中所讲的问题。
完整代码请移步:reverseLinkedList-test.ts
示例代码:
本文所列举的代码,其完整版请移步?:
- ReverseLinkedList.ts
- reverseLinkedList-test.ts
相关文章
- JDK中内嵌JS引擎介绍及使用
- 49195,npm最后的疯狂?盘点10款最有前途JavaScript构建工具
- 译文:5个增强Node.js应用程序增强功能
- 4个例子,吃透 JavaScript 实现的二叉搜索树 BST
- Vue中使用XML和JSON格式互转插件
- JDK中Jshell简单使用(JDK9版本以上或者JDK9版本)
- shiro中的JSP标签支持
- Java技术点-json转对象,对象转json
- SpringBoot+SpringDataJpa @Query之 JPQL使用书写模板(模糊查询and条件查询)
- Spring Boot中的Freemarker模版引擎引用css和js的正确姿势
- Node.js解压版的环境配置及相关常用命令
- JSP学习笔记(6)—— 自定义MVC框架
- JSP学习笔记(5)——Servlet、监听器、过滤器、MVC模式介绍
- Jsp学习笔记(4)——分页查询
- APIJSON简单使用
- JSP学习笔记(3)——JSTL 标签库
- JSP学习笔记(1)——Jsp指令、动作元素和内置对象
- JavaScript ES6 Promise对象
- Web前端——JavaScript扩展补充
- Web前端——表单提交和Js添加选项