这是前端食堂的第35篇原创
「口味:蒜蓉荷兰豆」
「烹饪时间:8min」
本文已收录在前端食堂同名仓库
Github
github.com/Geekhyt,欢迎光临食堂,如果觉得酒菜还算可口,赏个 Star 对食堂老板来说是莫大的鼓励。
数组想必大家都很熟悉,几乎我们每天都会操作它。那么我们就来对比数组来学习链表,首先要明确的是,链表和数组的底层存储结构不同,数组要求存储在一块连续的内存中,而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求降低了,但是随机访问的性能就没有数组好了,需要 O(n) 的时间复杂度。
下图中展示了单链表及单链表的添加和删除操作,其实链表操作的本质就是处理链表结点之间的指针。
在删除链表结点的操作中,我们只需要将需要删除结点的前驱结点的 next 指针,指向其后继即可。这样,当前被删除的结点就被丢弃在内存中,等待着它的是被垃圾回收器清除。
为了更便于你理解,链表可以类比现实生活中的火车,火车的每节车厢就是链表的一个个结点。车厢之间相互连接,可以添加或者移除掉。春运时,客运量比较大,列车一般会加挂车厢。
链表的结点结构由数据域和指针域组成,在 JavaScript 中,以嵌套的对象形式实现。
{
// 数据域
val: 1,
// 指针域
next: {
val:2,
next: ...
}
}
掌握了链表的基础知识后,我们拿几道链表的 LeetCode 真题练练手。
N+M 是两条链表的长度
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;
}
};
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;
};
const hasCycle = function(head) {
while (head) {
if (head.flag) {
return true;
} else {
head.flag = true;
head = head.next;
}
}
return false;
}
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;
};
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;
};
const middleNode = function(head) {
let fast = head;
let slow = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;