数据结构（四）链表
链表是什么？
- 多个元素组成的列表
- 元素存储不连续，用next指针连在一起
数组 VS 链表
- 数组：增删非首尾元素时往往需要移动元素
- 链表：增删非首尾元素，不需要移动元素，只需要更改next指向即可
JS中的链表
- JavaScript中没有链表
- 可以用Object模拟链表
Coding Part
LeetCode #237 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 1：
- 输入：head = [4,5,1,9], node = 5
- 输出：[4,1,9]
- 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2：
- 输入：head = [4,5,1,9], node = 1
- 输出：[4,5,9]
- 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
提示：
- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
解题思路：
- 无法直接获取被删除节点的上个节点
- 将被删除节点转移到下个节点 即：如果要删除1节点 则需要先把9节点的值赋值给1节点，即4-5-9-9，然后删除最后一个节点 即 4-5-9
解题步骤：
- 将被删除的节点的值改为下个节点的值
- 删除下个节点
复杂度：
- 时间复杂度O（1）
- 空间复杂度O（1）
/*
* @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;
// 删除一个节点即 将本来要删除的节点的指针 指向下个节点的下个节点。
};LeetCode #206 反转链表
反转一个单链表。
示例:
- 输入: 1->2->3->4->5->NULL
- 输出: 5->4->3->2->1->NULL
解题思路
- 假如：反转两个节点：将n+1的next指向n
- 假如：反转多个节点：双指针遍历链表，重复上述操作
解题步骤：
- 双指针一前一后遍历链表
- 遍历过程中不断反转双指针
复杂度：
- 时间复杂度 O（n）
- 空间复杂度 O（1）
/** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let p1 = head; let p2 = null; while(p1){ const temp = p1.next; p1.next = p2; p2 = p1; p1 = temp; } return p2; };
LeetCode #83 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 :
- 输入: 1->1->2
-
输出: 1->2
- 输入: 1->1->2->3->3
- 输出: 1->2->3
解题思路：
- 因为 链表是有序的，所以重复元素一定相邻
- 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
解题步骤：
- 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
- 遍历结束以后，返回原链表的头部
复杂度：
- 时间复杂度：O（n）
- 空间复杂度：O（1）
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
let p = head;
while(p && p.next){
if(p.val === p.next.val){
p.next = p.next.next;
}else{
p = p.next;
}
}
return head;
};LeetCode # 141 环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false
示例一：
- 输入：head = [3,2,0,-4], pos = 1
- 输出：true
- 解释：链表中有一个环，其尾部连接到第二个节点
示例二：
- 输入：head = [1,2], pos = 0
- 输出：true
- 解释：链表中有一个环，其尾部连接到第一个节点。
示例三：
- 输入：head = 1, pos = -1
- 输出：false
- 解释：链表中没有环。
提示：
- 链表中节点的数目范围是 [0, 104]
- -105 <= Node.val <= 105
- pos 为 -1 或者链表中的一个 有效索引 。
解题思路:
- 两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈。
- 用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈
解题步骤:
- 用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true
- 遍历结束后，还没有相逢就返回false
复杂度:
- 时间复杂度 O（n）
- 空间复杂度 O（1）
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let p1 = head; // 慢指针
let p2 = head; // 快指针
while(p1 && p2 && p2.next){
p1 = p1.next;
p2 = p2.next.next;
if(p1 === p2){ //两个指针相逢
return true;
}
}
return false;
};前端与链表：JS中的原型链
原型链介绍
- 原型链的本质是链表
- 原型链上的节点是各种原型对象，比如Function.prototype、Object.prototype
- 原型链通过_proto_属性连接各种原型对象
原型链长啥样？
- obj -> Object.prototype -> null
- func -> Function.prototype -> Object.prototype -> null
- arr -> Array.prototype -> Object.prototype -> null
Coding Part
原型链知识点
- 如果A沿着原型链能找到B.prototype，那么A instanceof B 为true
- 如果在A对象上没有找到x属性，那么会沿着原型链找x属性
面试题一
简述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属性。
console.log(foo.a); // 'value a' console.log(foo.b); // 'undefined' console.log(F.a); // 'value a' console.log(F.b); // 'value b'
前端与链表： 使用链表指针获取JSON的节点值
const json = {
a: { b: {c: 1} },
d: { e: 2 }
}
const path = ['d', 'e']; // 路径
// 和遍历链表异曲同工之妙
let p = json;
path.forEach(k =>{
p = p[k];
})
// 路径：2链表--总结
- 链表里的元素存储不是连续的，之间通过next链接
- JavaScript中没有链表，但可以用Object模拟链接
- 链表常用操作：修改next，遍历链表
- JS中的原型链也是一个链表。沿着proto属性
- 使用链表指针可以获取JSON的节点值
阶段思考题：
- 编写一个 instanceOf 方法，可以判断一个变量是否是另一个变量的实例。
- 判断一个链表是否为回文链表。题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/
