写在开头
最近数十天里，在广州狠狠经历了一波回南天、阴天、雨天，今天终于见着太阳了🔆，心情舒畅。
🌦️ 🌥️ 🌤️ ☀️ 🔆
不过，看新闻说"渣南"很快又会回来❗😭😭😭
何为链表
链表是数据结构中的一种基本类型，它与数组一样，可以用于存储一系列的元素。
链表是由一系列节点（Node）组成的集合，每个节点都包含两个部分：一个是存储数据的数据域，另一个是存储下一个节点地址的指针域。链表的节点不一定是连续存储的，因此它不需要像数组那样占用连续的内存空间。
太官方，不懂？😐
没事，上图，画得不好，将就看哈。🤡
代码形式上的表现：
const linkedList = {
data: 10,
next: {
data: 20,
next: {
data: 30,
next: null,
}
}
}
这是一个最基础的链表，它有三个节点。
优缺点
从上可以看到，链表有自己的一些特有优点😃，如：
- 灵活性： 链表的长度不是固定的，可以根据需要动态地增删节点。
- 非连续存储：链表的节点在内存中不必连续存储，可以有效地利用碎片化的内存空间。（Em...这点很重要）
- 插入和删除操作：链表的插入和删除操作只需要改变相应节点的指针域，不需要像数组那样移动其他元素。（部分场景效率会比数组高，时间复杂度都是O(1)）
而它也有一个相对严重的缺点😐，链表访问任何一个节点的时候，都需要从头开始寻找，无法直接通过下标直接去访问节点。
呃......虽然链表在日常的业务开发中基本是不会用到的，更别说去考虑这些优缺方面的事情了，但是，奈何面试要考呀，还是要了解了解的。
三种分类
单向链表：每个节点只包含一个指向下一个节点的指针。
（上面讲过，就不多讲啦。👻）
双向链表：每个节点包含两个指针，分别指向前一个节点和后一个节点。
代码形式上的表现：
function Node(data) {
this.data = data;
this.next = null;
this.prev = null;
}
// 创建节点
let node1 = new Node(10);
let node2 = new Node(20);
let node3 = new Node(30);
// 连接节点
node1.next = node2;
node2.prev = node1;
node2.next = node3;
node3.prev = node2;
由于双向链表不好直接用单纯的链表数据呈现（会更复杂😵），不过上面代码应该也比较好理解哈，重点在连接节点的步骤，也可以自己打印 node1 链表看看就能明白啦。
循环链表：链表中最后一个节点的指针指向第一个节点，形成一个环。
（循环链表和单向链表差不多，只是最后又拐了回来👻）
代码形式上的表现：
...
node1.next = node2;
node2.next = node3;
node3.next = node1; // 拐回去就行
遍历
说了那么多，肯定绕不过去的一个话题"遍历"，遍历一个链表的形式有多种多样。
下面，小编写了一个比较简单的单向链表的遍历作用示例，可以瞧瞧😉：
function Node(data) {
this.data = data;
this.next = null;
this.prev = null;
}
let node1 = new Node(10);
let node2 = new Node(20);
let node3 = new Node(30);
node1.next = node2;
node2.next = node3;
// 获取链表的所有节点数据
function getLinkedListData(list) {
let currentNode = list;
let result = '';
while (currentNode) {
// TODO: 实际业务
result += currentNode.data + (currentNode.next ? ' -> ' : '');
// 遍历每个节点
currentNode = currentNode.next;
}
return result;
}
const result = getLinkedListData(node1);
console.log(result); // 10 -> 20 -> 30
扯了这么多，相信你对链表也有一定了解了，足够应付大部分链表相关的事情了。
而接下来的内容，是小编前天在某家公司面试时遇到的两道链表的题目。
前面也已经写过一篇面试相关的文章了，也可以瞧瞧哈。👉 两道JS面试题🤡🤡🤡
链表反转
第一道目大概意思是要将一个链表反转过来，详细细节小编也记不太清了。当时反正是做一套卷子，搞得好像考试一样，唉。😐
但由于小编准备的面试八股文中并没有关于链表的内容，一开始也很懵逼，只能开始一点点去回忆链表的知识，最后硬着头皮咔咔一顿乱写，反正就是宁愿写错，也不要空着就是了😁。
下面是后来重新做的结果，可以瞧瞧：
function newNode(data, next) {
this.data = (data === undefined ? null : data);
this.next = (next === undefined ? null : next);
}
function reverse(list) {
// 保存反转后的链表
let result = null;
let currentNode = list;
while (currentNode) {
if (result) {
// 2. 创建新节点，指向上一个节点
result = new newNode(currentNode.data, result);
} else {
// 1. 从第一个节点开始
result = new newNode(currentNode.data, null);
}
// 遍历每个节点
currentNode = currentNode.next;
}
return result;
}
这个原理还是比较简单的，遍历链表每个节点，再重新生成新节点，重新连接节点即可。
你可以尝试把上面生成过的 node1 链表传入试试，再去对比结果看看。
链表排序
第二道题目就比较麻烦一点了，要求对一个链表进行排序，以节点的 data 属性进行升序，data 属性是一个数字来着，大概就是这个意思叭，也不知道面试官上哪里找来的题目。😗
这相对于考察的是对链表更细致的一些使用了，但小编当时没有做出来，也是乱写一通而已😅。
结果应该是这样子：
function Node(data) {
this.data = data;
this.next = null;
}
let node1 = new Node(12);
let node2 = new Node(3);
let node3 = new Node(40);
let node4 = new Node(19);
let node5 = new Node(6);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
function newNode(data, next) {
this.data = (data === undefined ? null : data);
this.next = (next === undefined ? null : next);
}
function sort(list) {
if (!list) return null;
let currentNode = list;
// 存储所有节点的数据
let dataArray = [];
while (currentNode) {
dataArray.push(currentNode.data);
// 遍历所有节点
currentNode = currentNode.next;
}
// 将节点数据进行排序
dataArray.sort((a, b) => a - b);
// 重新开始生成节点
let firstNode = new newNode(dataArray[0]);
list = firstNode;
// 每个目标节点
let temp = list;
for (let i = 1; i < dataArray.length; i++) {
let node = new newNode(dataArray[i]);
temp.next = node;
// 不段把新的目标节点放置在temp上，等待连接下一个节点
temp = temp.next;
}
return list;
};
const result = sort(node1);
console.log('排序前的链表：', node1);
console.log('排序后的链表：', result);
具体代码可以看看其中的注释，大概就介绍到这里啦。
对了对了，还有，在广州的大佬如有前端坑位，求捞，感谢感谢。😖
至此，本篇文章就写完啦，撒花撒花。
希望本文对你有所帮助，如有任何疑问，期待你的留言哦。
老样子，点赞+评论=你会了，收藏=你精通了。
