数据结构之“链表”
- 链表是什么？
- 数组 vs 链表
- JS中的链表
- LeetCode：237.删除链表中的节点
- LeetCode：206.反转链表
- LeetCode：2.两数相加
- LeetCode：83.删除排序链表中的重复元素
- LeetCode：141.环形链表
- 前端与链表（JS中的原型链）
-
- 一、instanceof的使用，并用代码实现
- 二
- 前端链表：使用链表指针获取JSON的节点值
- 总结
- 思考题
链表是什么？
多个元素组成的列表
元素存储不连续，用next指针连在一起
数组 vs 链表
数组：增删非首尾元素是往往需要移动元素
链表：增删非首尾元素，不需要移动元素，只需要更改next的指向即可
JS中的链表
JavaScript中没有链表
可以用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;
while (p) {
console.log(p.val);
p = p.next;
}
// 插入
const e = { val: 'e' };
c.next = e;
e.next = d;
// 删除
c.next = d;
LeetCode：237.删除链表中的节点
解题思路
无法直接获取被删除节点的上个节点
将被删除节点转移到下个节点
解题步骤
将被删节点的值改为下个节点的值
删除下个节点
时间复杂度O(1)，空间复杂度O(1)
LeetCode：206.反转链表
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
解题思路
反转两个节点：将n + 1的next指向n
反转多个节点：双指针遍历链表，重复上述操作
解题步骤
双指针一前一后遍历链表
反转双指针
时间复杂度O(n)，空间复杂度O(1)
LeetCode：2.两数相加
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解题思路
小学数学题，模拟相加操作
需要遍历链表
解题步骤
新建一个空链表
遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数留到下一位去相加
时间复杂度O(n)，空间复杂度O(n)
LeetCode：83.删除排序链表中的重复元素
输入：1 -> 1 -> 2
输出：1 -> 2
解题思路
因为链表是有序的，所以重复元素一定相邻
遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
解题步骤
遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
遍历结束后，返回原链表的头部
时间复杂度O(n)，空间复杂度O(1)
LeetCode：141.环形链表
解题思路
两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈
用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈
解题步骤
用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true
遍历结束后，还没有相逢就返回false
时间复杂度O(n)，空间复杂度O(1)
前端与链表（JS中的原型链）
原型链简介
原型链的本质是链表
原型链上的节点是各种原型对象，比如Function.prototype、Object.prototype…
原型链通过__proto__属性链接各种原型对象
原型链长啥样
obj -> Object.prototype -> null
func -> Function.prototype -> Object.prototype -> null
arr -> Array.prototype -> Object.prototype -> null
原型链知识点
如果A沿着原型链能找到B的原型对象（B.prototype），那么A instanceof B为true
如果在A对象上没有找到x属性，那么会沿着原型链找x属性
const obj = {}
const func = () => {}
const arr = []
//原型链通过__proto__属性链接各种原型对象
console.log(obj .__proto__ === Object.prototype) //true
console.log(func.__proto__ === Function.prototype) //true
console.log(func.__proto__.__proto__ === Object.prototype) //true
console.log(arr.__proto__ === Array.prototype) //true
console.log(arr.__proto__.__proto__ === Object.prototype) //true
//如果A沿着原型链能找到B的原型对象（B.prototype），那么A instanceof B为true
console.log(func instanceof Function) //true
console.log(func instanceof Object) //true
//fuc的proto属性指向Function的原型对象，
//func即是object的实例，也是function的实例
//如果在A对象上没有找到x属性，那么会沿着原型链找x属性
const obj = {};
Object.prototype.x = 'x'
const func = () => {};
Function.prototype.y = 'y'
console.log(obj.x) //x
console.log(obj.y) //undefined
console.log(func.x) //x
console.log(func.y) //y
一、instanceof的使用，并用代码实现
分析
知识点：如果A沿着原型链能找到B.prototype，那么A instanceof B为true
解法：遍历A的原型链，如果找到B.prototype，返回true，否则返回false
const instanceOf = (A,B) => {
let p = A;
while (p) {
if (p === B.prototype) {
return true;
}
p = p.__proto__;
}
return false;
}
二
var foo = {},F = Function(){};
Object.prototype.a = 'value a';
Function.prototype.b = 'value b'
console.log(foo.a)
console.log(foo.b)
console.log(F.a)
console.log(F.b)
分析
知识点：如果在A对象上没有找到x属性，那么会沿着原型链找x属性
解法：明确foo和F变量的原型链，沿着原型链找a属性和b属性
前端链表：使用链表指针获取JSON的节点值
const json = {
a: { b: { c: 1 } },
d: { e: 2 },
}
const path = ['a', 'b' ,'c']
let p =json;
path.forEach(k => {
p = p[k];
})
总结
链表里的元素存储不是连续的，之间通过next连接
JavaScript中没有链表，但可以用Object模拟链表
链表常用操作：修改next、遍历链表
JS中的原型链也是一个链表
使用链表指针可以获取JSON的节点值
思考题
1、编写一个 instanceOf 方法，可以判断一个变量是否是另一个变量的实例
2、请判断一个链表是否为回文链表。题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/