Hello, 各位怯懦的小伙伴, 大家好, 我是你们的嘴强王者小五, 身体健康, 脑子没病.
自己有丰盛的脱发技巧, 能让你一跃成为资深大咖.
一看就会一写就废是自己的宗旨, 菜到抠脚是自己的特点, 低微中透着一丝丝坚强, 傻人有傻福是对我最大的刺激.
欢送来到
小五的算法系列之链表.
前言
此系列文章以《算法图解》和《学习JavaScript算法》两书为外围，其余材料为辅助，并佐以笔者愚见所成。力求以简略、趣味的语言带大家领略这算法世界的微妙。
本文内容为链表。笔者将率领大家从 js 模仿其实现登程，逐渐变动以摸索链表的其它模式，最初附上几道习题加深了解及坚固所学。
链表在 JavaScript 中有一重要利用 -- 原型链，文章传送门 大话原型链。
链表简介
笔者从 “什么是链表” 及 “链表用来干什么” 来给大家文言文言
什么是链表
链表就像寻宝游戏，宝物藏在小岛各处。游戏开始时会失去一条线索，通过手中线索去寻找下一个宝物的地点，顺次类推。
由此咱们总结下链表的特点:
- 宝物扩散在小岛各处 - 链表中的元素在内存中的存储地位并不间断
- 通过线索确定下一个地点 - 每个节点由存储元素自身及指向下一元素的指针组成，无奈越过某一节点达到下一节点
用来干什么
用来存储数据，此时你小小的脑袋上是不是有大大的问号，存储数据为什么不必数组呢?
咱们来联合各自特点比对下两种数据结构的优缺点:
数组存储地位间断，而链表不间断
如果在数组两头插入一个元素会怎么 数组是间断的，就像插队一样，其余人都要向后一位；而链表存储不间断，插入时其余元素无需变动，删除同理；
故可得出结论：插入或删除元素时，链表比数组更有劣势
数组间接拜访元素，而链表通过指针寻找元素
因数组存储间断，咱们可间接通过下标对其拜访；而链表则须要从表头开始逐个寻找，直至找到；
故可得出结论：查找元素时，数组比链表更有劣势
链表实现
咱们接下来用js模仿一个链表，并为其增加如下办法：
append(element)：向链表尾部追加新元素insert(element, position)：向链表特定地位插入新元素remove(element)：从链表中移除某一元素indexOf(element)：返回元素在链表中的索引, 若没有该元素则返回-1removeAt(position)：从链表特定地位移除一个元素isEmpty()：链表中是否存在元素size()：链表中元素个数
对链表而言，无论是插入操作还是删除操作，均是扭转next指针指向的过程。
构造
首先咱们来定义下链表中的节点，应蕴含其元素自身element及指向下一节点的指针next
class Node<T> { element: T | null; next: Node<T> | null; constructor(element: T | null) { this.element = element; this.next = null; }}在来明确下链表构造，其须要有一个头部节点head，及一个记录长度的length
class LinkedList<T> { head: Node<T> | null = null; length = 0;}append(element)
若空，则其为头部节点；若非空，则其为链表尾部节点；
append(element: T) { let node = new Node<T>(element); if (!this.head) { this.head = node; } else { let current = this.head; while (current.next) { current = current.next; } current.next = node; } this.length++;}insert(element, position)
找到插入地位，更改next指向
- position = 0，
node.next -> head - position > 0，
previous.next -> node, node.next -> current
insert(element: T, position: number) { if (position < 0 || position > this.length) return false; let node = new Node<T>(element); let index = 0; let current = this.head; let previous: Node<T> | null = null; if (position === 0) { node.next = this.head; this.head = node; } else { while (current && index++ < position) { previous = current; current = current.next; } (previous as Node<T>).next = node; node.next = current; } this.length++; return true;}removeAt(position)
思路同insert，找到插入地位，更改next指向
- position = 0，
head -> head.next - position > 0，
previous.next -> current.next
removeAt(position: number) { if (!this.head || position < 0 || position >= this.length) return false; let index = 0; let current: Node<T> | null = this.head; let previous: Node<T> | null = null; if (position === 0) { this.head = this.head.next; } else { while (current && index++ < position) { previous = current; current = current.next; } (previous as Node<T>).next = current?.next || null; } this.length--; return true;}indexOf(element)
从头遍历链表即可
indexOf(element: T) { let current = this.head; let index = 0; while (current) { if (typeof current.element === 'object') { if (JSON.stringify(element) === JSON.stringify(current.element)) return index; } else { if (element === current.element) return index; } current = current.next; index++; } return -1;}remove(element)
整合removeAt和indexOf即可
remove(element: T) { let position = this.indexOf(element); return this.removeAt(position);}双向链表
字面意思阐明所有，一个连贯为双向的链表；可抉择 “从头遍历至尾” 亦或 “从尾遍历至头”；
故咱们为Node类追加一个prev指针，为链表减少一个tail属性，改写以下三个办法append、insert、removeAt
tips：只有留神好其指针的连贯即可，切莫丢三落四只连贯了一个方向
append(element)
- 若为空，则
head = node、tail = node - 若非空，则
tail.next = node，node.prev = tail；而后更新tail即可
append(element: T) { let node = new Node<T>(element); if (!this.head || !this.tail) { this.head = node; this.tail = node; } else { this.tail.next = node; node.prev = this.tail; this.tail = node; } this.length++;}insert(element, position)
- 插入头部或尾部，思路同追加元素，思考好边界值即可
- 插入两头，next链：
prevNode.next = node->node.next = nextNode；prev链：nextNode.prev = node->node.prev = prevNode；
insert(element: T, position: number) { if (position < 0 || position > this.length) return false; let node = new Node<T>(element); if (position === 0) { if (this.head) { this.head.prev = node; node.next = this.head; this.head = node; } else { this.head = node; this.tail = node; } } else if (position === this.length) { (this.tail as Node<T>).next = node; node.prev = this.tail; this.tail = node; } else { let current = this.head; let previous: Node<T> | null = null; let index = 0; while (current && index++ < position) { previous = current; current = current.next; } (previous as Node<T>).next = node; node.next = current; (current as Node<T>).prev = node; node.prev = previous; } this.length++;}removeAt(position)
思路根本和insert统一
- 若链表仅有一个节点，头尾节点别离赋null
- 删除头部：
head = head.next、head.prev = null，尾部同理 - 删除两头
preNode.next = nextNode、nextNode.prev = preNode
removeAt(position: number) { if (!this.head || position < 0 || position >= this.length) return false; if (position === 0) { if (this.length === 1) { this.head = null; this.tail = null; } else { this.head = this.head.next; (this.head as Node<T>).prev = null; } } else if (position === this.length - 1) { this.tail = (this.tail as Node<T>).prev; (this.tail as Node<T>).next = null; } else { let current: Node<T> | null = this.head; let previous: Node<T> | null = null; let index = 0; while (current && index++ < position) { previous = current; current = current.next; } if (!previous || !current) return false; previous.next = current.next; (current.next as Node<T>).prev = previous; } this.length--; return true;}循环链表
正如其名，首尾相连即造成了循环链表 tailNode.next = head；实现时留神好边界值的解决即可，尤其是波及首尾元素的解决；思维上与上文实现基本一致，大家无妨入手试试看。
双脚奉上单循环链表的代码连贯：单循环链表
小试牛刀
以下题目均来自 LeetCode，笔者会为每道题目提供一种解题思路；此思路绝非最佳，欢送各位看官积极思考，并留下本人的独特见解。
鉴于题干较长，请点击题目查看具体题目。
下文所有 ListNode 格局如下:
class ListNode { val: number next: ListNode | null constructor(val?: number, next?: ListNode | null) { this.val = (val === undefined ? 0 : val) this.next = (next === undefined ? null : next) }}LeetCode 141. 环形链表
题目简述
入参为头节点，判断是否可成环。
题目剖析
判断是否成环，第一想法为借用长度，若超出长度仍可循环，则有环。
let index = 0;let current = head;while (current) { if (index > size) return true; current = current.next; index++;}return false;但此题入参仅有头节点，得换个思路；一个指针必然行不通，没有突破循环的条件，有环岂不是死循环了；那咱们借助两个指针，一快一慢，想不明确的话能够类比下时钟或者跑步压圈，如若有环，一快一慢必然相遇。
代码实现
const hasCycle = (head: ListNode | null): boolean => { let slow = head; let fast = head; while (slow && fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { return true; } } return false;};LeetCode 2. 两数相加
题目简述
下图为两个逆序存储的链表，代表：342 + 465 = 807
入参：两个链表的头部 l1、l2，求新生成链表 (sum的链表模式)
题目剖析
笔者看到此题，首先想到的是，别离遍历两个链表，取到对应数字，相加后存入新链表；当笔者兴致冲冲的提交后，大数了，若在我的项目中能够 big.js 等解决下大数，这毕竟是练习题，咱们尝试换个思路。
遍历l1 -> 获取 342遍历l2 -> 获取 465342 + 465 = 807807 存入链表 7 -> 0 -> 8这就是一个手写加法运算的过程，咱们按位相加，2 + 5 = 7，4 + 6 = 10 即 0 进位 1，3 + 4 + 进位1 = 8
- 遍历l1、l2，按位相加
- 新增变量代表是否进位，若进位则加1
- 留神最初若仍旧有进位，需补1，如:
89 + 13 = 102-------------9 83 1-----2 0 1代码实现
const addTwoNumbers = ( l1: ListNode | null, l2: ListNode | null,): ListNode | null => { let current1 = l1; let current2 = l2; let carryOver = 0; // 进位 let sum: ListNode = new ListNode(); // sum链, 给个默认头部, 最初取next即可 let current: ListNode | null = sum; while (current1 || current2) { // 两链表未必等长 如 999 + 1 let currentSum = (current1?.val || 0) + (current2?.val || 0) + carryOver; carryOver = 0; if (currentSum >= 10) { carryOver = 1; currentSum -= 10; } current.next = new ListNode(currentSum); current1 = current1?.next || null; current2 = current2?.next || null; current = current.next; } if (carryOver > 0) current.next = new ListNode(carryOver); return sum.next;};LeetCode 24. 两两替换链表中的节点
题目简述
给定一个链表，两两替换其中相邻的节点，并返回替换后的链表
入参：链表头节点
题目剖析
链表问题实质都是拨弄指针的问题，以1、3、4两两调换为例
[1, next: 3] [3, next: 4], [4, next: null]------------------------------------------[1, next: 3] -> [1, next: 4][4, next: null] -> [4, next: 3][3, next: 4 -> [3, next: null]留神下边界值，首次循环时解决的只有两个节点，且需记录新的 head 值
代码实现
const swapPairs = (head: ListNode | null): ListNode | null => { let previous: ListNode | null = null; let current = head; let index = 0; // 记录是否为首次循环 while (current && current.next) { previous = current; current = current.next; if (index === 0) { previous.next = current.next; current.next = previous; head = current; // 替换后扭转头部的值 } if (index > 0 && current.next) { let node = current; current = current.next; node.next = current.next; previous.next = current; current.next = node; } current = current.next; index++; } return head;}后记
本文代码 Github 链接：链表
本系列其它文章链接：起航篇 - 排序算法 、 栈与队列