侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 140 篇文章
  • 累计创建 25 个标签
  • 累计收到 38 条评论

目 录CONTENT

文章目录

实现链表反转

神奇的程序员
2022-06-16 / 0 评论 / 1 点赞 / 186 阅读 / 1,898 字

前言

有一个链表,如何将其反转并获取反转后的链表头节点?本文将分享一种解决方案,欢迎各位感兴趣的开发者阅读本文。

思路分析

经过数据结构基础的学习,我们知道链表中每个节点都会有一个指针,用于指向它的下一个节点,那么,我们只需要从链表头部开始遍历,逐一修改它的指针指向至其上一个节点,即可完成链表的反转。

这个思路的难点在于如何调整指针的指向,我们可以借助3个指针来完成这个操作,如下所示:

  • p1、p3分别是p2指针的上、下一个节点(默认指向null)
  • 如果p2指针指向的节点不为null
    • 获取p2指针指向的下一个节点,将其保存至p3
    • 如果p3的值为null,则表示链表已经反转完毕,用一个变量存储p2的值
    • 修改p2指针的指向至p1,修改p1的值为p2,修改p2的值为p3

IMG_12BA2C91C60A-1

实现代码

通过上面的分析,我们分析出了可以用三指针来解决问题的思路,接下来,我们来看下代码实现。

首先,设计一个名为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);

运行结果如下所示,成功的解决了文章前言中所讲的问题。

image-20220615221918607

完整代码请移步👉:reverseLinkedList-test.ts

注意:上述代码中用到的LinkedList是自定义的一个类,它实现了链表这个数据结构,对其原理感兴趣的开发者请移步我的另一篇文章👉:链表与变相链表的实现

示例代码

本文所列举的代码,其完整版请移步👇:

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
1

评论区