原文链接：https://note.noxussj.top/?source=helloworld
什么是链表？
链表是有序的数据结构，链表中的每个部分称为节点。可以首、尾、中间进行数据存取，链表的元素在内存中不必是连续的空间，每个节点通过 next 指针指向下一个节点。
优点
链表的添加和删除不会导致其余元素位移。
缺点
无法根据索引快速定位元素。
数组和链表区别
- 获取、修改元素时，数组效率高
- 添加、删除元素时，链表效率高
- 数组添加、移除会导致后续元素位移，性能开销大
环形链表
指的是链表最后一个节点的 next 指向第一个节点，形成首尾相连的循环结构。
链表环路检测
解题思路
- 快慢指针法实现
- slow 指针每次移动一位，fast 指针每次移动两位，如果他们相遇则说明链表存在环
- 新指针 ptr 从 head 开始移动，与 slow 相遇的位置即为环的起点
- 由 fast 指针移动距离为 slow 的两倍可得出公式： a + (nb + nc + b) = 2(a + b)
- 变化处理后得到新公式： a = (n - 1)(b + c) + c
实现功能
在 JavaScript 中没有链表，我们可以通过模拟一个类或者是通过 Object 实现链表的所有功能。
节点类
- value 当前节点值
- next 指向下一个节点
链表类
- addAtTail 尾部添加节点
- addAtHead 头部添加节点
- addAtIndex () 指定位置添加节点
- get 获取节点
- removeAtIndex () 删除指定节点
应用场景
- leetcode 两数相加
基础案例
通过对象实现
1// 链表 2let a = { val: 'a', next: null } 3let b = { val: 'b', next: null } 4let c = { val: 'c', next: null } 5let d = { val: 'd', next: null } 6 7a.next = b 8b.next = c 9c.next = d 10 11// 尾部添加节点 12let e = { val: 'e', next: null } 13d.next = e 14 15// 头部添加节点 16let z = { val: 'z', next: null } 17z.next = a 18a = z 19 20// 指定位置添加节点 21let f = { val: 'f', next: null } 22c.next = f 23f.next = d 24 25// 删除指定节点 26d.next = null
通过类模拟实现
1/** 2 * 节点类 3 */ 4class Node { 5 constructor(value) { 6 this.value = value 7 this.next = null 8 } 9} 10 11/** 12 * 链表类 13 */ 14class Link { 15 constructor() { 16 this.head = null 17 this.count = 0 18 } 19 20 /** 21 * 尾部添加节点 22 */ 23 addAtTail(item) { 24 if (this.count === 0) { 25 this.head = new Node(item) 26 27 this.count++ 28 29 return this.head 30 } 31 32 let endNode = this.head 33 34 while (endNode.next) { 35 endNode = endNode.next 36 } 37 38 endNode.next = new Node(item) 39 40 this.count++ 41 42 return item 43 } 44 45 /** 46 * 头部添加节点 47 */ 48 addAtHead(item) { 49 if (this.head) { 50 const oldHead = this.head 51 52 this.head = new Node(item) 53 this.head.next = oldHead 54 } else { 55 this.head = new Node(item) 56 } 57 58 this.count++ 59 60 return item 61 } 62 63 /** 64 * 指定位置添加节点 65 */ 66 addAtIndex(index, item) { 67 if (this.isInvalidIndex(index) || !this.head) { 68 return -1 69 } 70 71 if (index === 0) { 72 this.addAtHead(item) 73 74 return item 75 } 76 77 let prev = this.head 78 79 while (index > 0) { 80 index-- 81 } 82 83 const next = prev.next 84 85 const cur = new Node(item) 86 87 prev.next = cur 88 cur.next = next 89 90 this.count++ 91 92 return item 93 } 94 95 /** 96 * 获取节点 97 */ 98 get(index) { 99 if (this.isInvalidIndex(index) || !this.head) { 100 return -1 101 } 102 103 let cur = this.head 104 105 while (index > 0) { 106 cur = cur.next 107 108 index-- 109 } 110 111 return cur 112 } 113 114 /** 115 * 删除指定节点 116 */ 117 removeAtIndex(index) { 118 if (this.isInvalidIndex(index) || !this.head) { 119 return -1 120 } 121 122 if (index === 0) { 123 const oldHead = this.head 124 this.head = this.head.next 125 126 this.count-- 127 128 return oldHead 129 } 130 131 let prev = this.head 132 133 while (index - 1 > 0) { 134 prev = prev.next 135 136 index-- 137 } 138 139 const cur = prev.next 140 141 prev.next = cur.next 142 143 this.count-- 144 145 return cur 146 } 147 148 /** 149 * 判断index是否为空，是否超出数据长度大小 150 */ 151 isInvalidIndex(index) { 152 if (index === '' || index === null || index === undefined || index < 0 || index > this.count - 1) { 153 return true 154 } 155 156 return false 157 } 158} 159 160const link = new Link() 161 162link.addAtTail('a') 163link.addAtTail('b') 164link.addAtTail('c')