链表
大约 6 分钟约 1900 字
简介
::: warning 注意 链表头就是一个链表，因为链表是一个串，你拿起来头，自然拿起来一串 :::
多个元素组成的列表。
元素存储不连续，用 next 指针连在一起。
在数组中增删非首尾元素时往往需要移动元素，链表在增删非首尾元素，不需要移动元素，只需要更改 next 的指向即可。
js 中没有链表，需要用 Object 模拟:
const a = { val: 'a' }
const b = { val: 'b' }
const c = { val: 'c' }
const d = { val: 'd' }
// 创建
a.next = b
b.next = c
c.next = d
// 遍历
let p = a //声明一个指针指向a
while (p) {
console.log(p.val)
p = p.next
}
// 插入e
const e = { val: 'e' }
c.next = e
e.next = d
console.log(a)
// 删除e
c.next = d
LeetCode：237.删除链表中的节点
- 解题思路
无法直接获取被删除节点的上个节点
把要删除的下个结点的值赋给被删除节点，然后将被删除节点的下一节点删除
比如 1-2-3-4 要删除 3，先 1-2-4-4 然后删除最后一个 4，最后变成 1-2-4
- 解题步骤
将被删节点的值改为下个节点的值。
删除下个节点。
/*
* @lc app=leetcode.cn id=237 lang=javascript
*
* [237] 删除链表中的节点
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} node
* @return {void} Do not return anything, modify node in-place instead.
*/
var deleteNode = function (node) {
node.val = node.next.val
node.next = node.next.next
}
// @lc code=end
LeetCode：206.反转链表
- 解题思路
反转两个节点：将 n+1 的 next 指向 n
反转多个节点：双指针遍历链表，重复上述操作。
- 解题步骤
双指针一前一后遍历链表。
反转双指针。
::: details 解法一
/*
* @lc app=leetcode.cn id=206 lang=javascript
*
* [206] 反转链表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let [p1, p2] = [head, null]
while (p1) {
let tmp = p1.next
p1.next = p2
p2 = p1
p1 = tmp
}
return p2
}
// @lc code=end
:::
::: details 解法二
/*
* @lc app=leetcode.cn id=206 lang=javascript
*
* [206] 反转链表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let [p1, p2] = [head, null]
while (p1) {
;[p1.next, p2, p1] = [p2, p1, p1.next]
}
return p2
}
// @lc code=end
:::
LeetCode：2. 两数相加
- 解题思路
小学数学题，模拟相加操作
需要遍历链表
- 解题步骤
新建一个空链表
遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数留到下一位去相加
/*
* @lc app=leetcode.cn id=2 lang=javascript
*
* [2] 两数相加
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
let l3 = new ListNode()
let [p1, p2, p3, carry] = [l1, l2, l3, 0]
while (p1 || p2) {
let v1 = p1 ? p1.val : 0
let v2 = p2 ? p2.val : 0
let val = v1 + v2 + carry
carry = Math.floor(val / 10)
p3.next = new ListNode(val % 10)
if (p1) p1 = p1.next
if (p2) p2 = p2.next
p3 = p3.next
}
if (carry) p3.next = new ListNode(carry)
return l3.next
}
// @lc code=end
LeetCode：83. 删除排序链表中的重复元素
解题思路
因为链表是有序的，所以重复元素一定相邻
遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
解题步骤
遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
遍历结束后，直接返回原链表的头部(head)
/*
* @lc app=leetcode.cn id=83 lang=javascript
*
* [83] 删除排序链表中的重复元素
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function (head) {
let p1 = head
while (p1 && p1.next) {
if (p1.val === p1.next.val) {
p1.next = p1.next.next
} else {
p1 = p1.next
}
}
return head
}
// @lc code=end
LeetCode：141. 环形链表
- 解题思路
两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈
用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈。
- 解题步骤
用一快一慢两个指针遍历链表，如果指针能够相逢，就返回 true。
遍历结束后，还没有相逢就返回 false。
/*
* @lc app=leetcode.cn id=141 lang=javascript
*
* [141] 环形链表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
let [slow, fast] = [head, head]
while (slow && fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) return true
}
return false
}
// @lc code=end
LeetCode： 234. 回文链表
- 解题思路
回文就是反转以后和以前一样的就是回文结构，例如 1->2->3->2->1，我们将它反转之后还是与原链表一样，我们就称这种链表结构为回文结构
- 解题步骤
快慢指针，起初都指向表头，快指针一次走两步，慢指针一次走一步，遍历结束时：
要么，slow 正好指向中间两个结点的后一个。
要么，slow 正好指向中间结点。
用 prev 保存 slow 的前一个结点，通过prev.next = null断成两个链表。
将后半段链表翻转(参考 leetcode.206)，和前半段从头比对。
/*
* @lc app=leetcode.cn id=234 lang=javascript
*
* [234] 回文链表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
// 链表只有一个节点的情况
if (head.next == null) {
return true
}
let [fast, slow, prev] = [head, head, null]
while (fast && fast.next) {
prev = slow
slow = slow.next
fast = fast.next.next
}
// 断成两个链表
prev.next = null
// 翻转后半段
let head2 = null
while (slow) {
// 解构赋值，不用使用临时变量
// ;[slow.next, head2, slow] = [head2, slow, slow.next]
let temp = slow.next
slow.next = head2
head2 = slow
slow = temp
}
// 前后两段进行比较
while (head && head2) {
if (head.val !== head2.val) {
return false
}
head = head.next
head2 = head2.next
}
return true
}
// @lc code=end
前端与链表：JS 中的原型链
原型链的本质是链表。
原型链上的节点是各种原型对象， 比如 Function.prototype、 Object.prototype……
原型链通过__proto__属性连接各种原型对象。
面试题：instanceof 的原理，并用代码实现。
知识点：如果 A 沿着原型链能找到B.prototype，那么A instanceof B为 true。
解法：遍历 A 的原型链，如果找到B.prototype，返回 true，否则返回 false
面试题：看输出
const foo = {}
F = function () {}
Object.prototype.a = 'value a'
Function.prototype.b = 'value b'
console.log(foo.a)
console.log(foo.b)
console.log(F.b)
console.log(F.b)
知识点：如果在 A 对象上没有找到 ⅹ 属性，那么会沿着原型链找 ⅹ 属性。
解法：明确 foo 和 F 变量的原型链，沿着原型链找 a 属性和 b 属性。
前端与链表：使用链表指针获取 JSON 的节点值
const json = {
a: { b: { c: 1 } },
d: { e: 2 },
}
const path = ['d', 'e']
let p = json
path.forEach((k) => {
p = p[k]
})