面试链表不再怕
The following article is from 前端食堂 Author 霍语佳
（给前端大全加星标，提升前端技能）
作者： 前端食堂 公号 / 霍语佳
「观感度：🌟🌟🌟🌟🌟」
「口味：蒜蓉荷兰豆」
「烹饪时间：8min」
本文已收录在前端食堂同名仓库
Githubgithub.com/Geekhyt，欢迎光临食堂，如果觉得酒菜还算可口，赏个 Star 对食堂老板来说是莫大的鼓励。
链表
数组想必大家都很熟悉，几乎我们每天都会操作它。那么我们就来对比数组来学习链表，首先要明确的是，链表和数组的底层存储结构不同，数组要求存储在一块连续的内存中，而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求降低了，但是随机访问的性能就没有数组好了，需要 O(n) 的时间复杂度。
下图中展示了单链表及单链表的添加和删除操作，其实链表操作的本质就是处理链表结点之间的指针。
在删除链表结点的操作中，我们只需要将需要删除结点的前驱结点的 next 指针，指向其后继即可。这样，当前被删除的结点就被丢弃在内存中，等待着它的是被垃圾回收器清除。
为了更便于你理解，链表可以类比现实生活中的火车，火车的每节车厢就是链表的一个个结点。车厢之间相互连接，可以添加或者移除掉。春运时，客运量比较大，列车一般会加挂车厢。
链表的结点结构由数据域和指针域组成，在 JavaScript 中，以嵌套的对象形式实现。
{
// 数据域
val: 1,
// 指针域
next: {
val:2,
next: ...
}
}
名词科普
头结点：头结点用来记录链表的基地址，是我们遍历链表的起点 尾结点：尾结点的指针不是指向下一个结点，而是指向一个空地址 NULL 单链表：单链表是单向的，它的结点只有一个后继指针 next 指向后面的结点，尾结点指针指向空地址 循环链表：循环链表的尾结点指针指向链表的头结点 双向链表：双向链表支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点，双向链表会占用更多的内存，但是查找前驱节点的时间复杂度是 O(1) ，比单链表的插入和删除操作都更高效 双向循环链表
循环链表
双向链表
双向循环链表
LeetCode真题
掌握了链表的基础知识后，我们拿几道链表的 LeetCode 真题练练手。
1.合并两个有序链表
https://leetcode-cn.com/problems/merge-two-sorted-lists/
思路
使用递归来解题 将两个链表头部较小的一个与剩下的元素合并 当两条链表中的一条为空时终止递归
复杂度分析
N+M 是两条链表的长度
时间复杂度：O(M+N) 空间复杂度：O(M+N)
const mergeTwoLists = function (l1, l2) {
if (l1 === null) {
return l2;
}
if (l2 === null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};
2.环形链表
https://leetcode-cn.com/problems/linked-list-cycle/
思路
双指针法 使用快慢不同的两个指针遍历，快指针一次走两步，慢指针一次走一步 如果没有环，快指针会先到达尾部，返回 false 如果有环，则一定会相遇
复杂度分析
时间复杂度：O(N) 空间复杂度：O(1)
const hasCycle = function(head) {
if (!head || !head.next) {
return false;
}
let fast = head.next;
let slow = head;
while (fast !== slow) {
if (!fast || !fast.next) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
};
思路
标记法 遍历链表，通过标记判断是否有环，如果标记存在则有环。
复杂度分析
时间复杂度：O(N) 空间复杂度：O(1)
const hasCycle = function(head) {
while (head) {
if (head.flag) {
return true;
} else {
head.flag = true;
head = head.next;
}
}
return false;
}
3.反转链表
https://leetcode-cn.com/problems/reverse-linked-list/
思路
迭代 初始化前驱节点为 null，初始化目标节点为头节点 遍历链表，记录 next 节点并反转指针 prev 和 curr 指针分别往前移动一步 反转结束后，prev 成为新链表的头节点
复杂度分析
时间复杂度：O(N) 空间复杂度：O(1)
const reverseList = function(head) {
let prev = null;
let curr = head;
while (curr !== null) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
};
4.删除结点的倒数第 N 个节点
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
思路
删除倒数第 n 个结点，我们需要找到倒数第 n+1 个结点，删除其后继结点即可 添加 prev 结点，也称其为哨兵结点，处理边界问题 使用双指针法，快指针先走 n+1 步，然后快慢指针同步往前走，直到 fast.next 为 null 删除倒数第 n 个结点，返回 prev.next
复杂度分析
时间复杂度：O(N) 空间复杂度：O(1)
const removeNthFromEnd = function(head, n) {
let prev = new ListNode(0);
prev.next = head;
let fast = prev;
let slow = prev;
while (n--) {
fast = fast.next;
}
while (fast && fast.next) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return prev.next;
};
5.求链表的中间结点
https://leetcode-cn.com/problems/middle-of-the-linked-list/
思路
双指针法 使用快慢不同的两个指针遍历，快指针一次走两步，慢指针一次走一步 当快指针到达终点时，慢指针刚好走到中间
复杂度分析
时间复杂度：O(N) N 是给定链表的结点数目 空间复杂度：O(1) 只需要常数空间存放 slow 和 fast 两个指针
const middleNode = function(head) {
let fast = head;
let slow = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};觉得本文对你有帮助？请分享给更多人
关注「前端大全」加星标，提升前端技能
好文章，我在看❤️