前言
有一个链表，如何将其反转并获取反转后的链表头节点？本文将分享一种解决方案，欢迎各位感兴趣的开发者阅读本文。
思路分析
经过数据结构基础的学习，我们知道链表中每个节点都会有一个指针，用于指向它的下一个节点，那么，我们只需要从链表头部开始遍历，逐一修改它的指针指向至其上一个节点，即可完成链表的反转。
这个思路的难点在于如何调整指针的指向，我们可以借助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
注意：上述代码中用到的LinkedList是自定义的一个类，它实现了链表这个数据结构，对其原理感兴趣的开发者请移步我的另一篇文章👉：链表与变相链表的实现。
示例代码
本文所列举的代码，其完整版请移步👇：
写在最后
至此，文章就分享完毕了。
我是神奇的程序员，一位前端开发工程师。
如果你对我感兴趣，请移步我的个人网站，进一步了解。
- 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
- 本文首发于神奇的程序员公众号，未经许可禁止转载💌
评论区