天问博客
指南
文章
Hello
指南
文章
Hello

链表是一种 动态且零散 的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。本文介绍一下如何将数组变成链表，并且实现 反转单向链表 的算法。

数据结构与算法 · 反转单向链表

一、链表 VS 数组

  • 链表特点

数据结构与算法 · 链表

  • 链表 VS 数组

数据结构与算法 · 链表 VS 数组

二、数组转单向链表

  • TS 代码演示
interface ILinkListNode { value: number next?: ILinkListNode } type ItemNode = ILinkListNode | undefined function createLinkList(arr: number[]): ILinkListNode { const len = arr.length; if (len === 0) throw new Error('arr is empty'); let currNode: ILinkListNode = { value: arr[len - 1] } if (len===1) return currNode for (let i = len-2; i >= 0; i--) { currNode = { value: arr[i], next: currNode } } return currNode }

三、反转单向链表

  1. 反转单向链表思路图示

数据结构与算法 · 反转单向链表

  1. TS 代码演示
function reverseLinkList(listNode: ILinkListNode): ILinkListNode { let prevNode: ItemNode = undefined let currNode: ItemNode = undefined let nextNode: ItemNode = listNode while (nextNode) { // 第一个元素删掉 next ，防止循环引用 if (currNode && !prevNode) { delete currNode.next } // 反转指针 if (currNode && prevNode) { // @ts-ignore currNode.next = prevNode } // 指针整体向后移 prevNode = currNode currNode = nextNode nextNode = nextNode?.next } // 最后一个补充：当 nextNode 为空时，此时 currNode 尚未设置 next 指向 currNode!.next = prevNode return currNode! }

四、测试

const arr = [100, 200, 300, 400, 500] const res = createLinkList(arr) console.log(res) let str1 = JSON.stringify(res) let link1 = JSON.parse(str1) let list1 = reverseLinkList(link1) console.log(list1)

数组转链表输出：

{ "value": 100, "next": { "value": 200, "next": { "value": 300, "next": { "value": 400, "next": { "value": 500 } } } } }

反转链表输出：

{ "value": 500, "next": { "value": 400, "next": { "value": 300, "next": { "value": 200, "next": { "value": 100 } } } } }

《数据结构与算法》系列

  1. 什么是算法复杂度
  2. 堆(heap)、栈(stack)、队列(queue)
  3. 把一个数组旋转k步
  4. 判断字符串是否括号匹配
  5. 数组、栈、链表、队列结构与对比
  6. 用两个栈实现一个队列
  7. 反转单向链表
  8. 用链表实现队列
  9. 二分查找
  10. 查找两数之和

欢迎访问：天问博客