链表反转

2024-04-03
上海
本文字数：613 字
阅读完需：约 2 分钟

链表反转是指将一个单向链表中的节点顺序完全颠倒，即原链表的尾部变为新链表的头部，原链表的头部变为新链表的尾部。这意味着原链表中每个节点的指针方向都将被反转。例如，假设有一个链表 1 -> 2 -> 3 -> 4 -> 5，反转后变为 5 -> 4 -> 3 -> 2 -> 1。

链表反转通常是算法和数据结构中常见的一个问题，因为它涉及到指针的操作，可以帮助理解指针的使用和链表的基本操作。

双指针实现图解：

Code 实现

class ListNode<T> {   // TypeScript 中的属性声明 destination: 增强代码的可读性和可维护性，并提供类型检查的好处，防止不正确的类型使用  value: T;  // 泛型更为灵活  next: ListNode<T> | null = null;  constructor(value: T, next: ListNode<T> | null = null) {    this.value = value;    this.next = next;  }}
// 类本身可以作为一种类型使用function reverseLinkedList<T>(head: ListNode<T> | null): ListNode<T> | null {  let prev: ListNode<T> | null = null;  let curr: ListNode<T> | null = head;    while (curr !== null) {    const nextNode: ListNode<T> | null = curr.next; // 先存储下一个节点的引用    curr.next = prev; // 当前节点指向前一个节点，完成反转    prev = curr;  // prev向前移动一步    curr = nextNode; // curr向前移动一步  }
  return prev;}

复制代码

Reference:

动图出去：https://zhuanlan.zhihu.com/p/541077037

Come on, let's master programmer! ⛽️

发布于: 刚刚阅读数: 6

原文链接:【http://xie.infoq.cn/article/9b69e981f0feed2b2e7ac67a1】。

EchoZhou

关注

还未添加个人签名 2018-04-24 加入

还未添加个人简介

发布

暂无评论

创作场景

链表反转

双指针实现图解：

Code 实现

Reference:

EchoZhou

评论