链表
定义
与数组的对比
基本操作
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; // 当p有值时每次指向下一个
}
// 插入 将e插入c d中间
const e = { val: 'e' };
c.next = e;
e.next = d;
// 删除 e
c.next = d;
刷题
LeetCode: 237.删除链表中的节点
题目描述
解题思路
为删除节点1： 将最后的节点9 复制给节点1， 此时链表变为 4 5 9 9 ，然后删除下个节点9 即可。
解题步骤
Code
/**
* 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; // 删除节点
};
时间复杂度 空间复杂度分析
- 因其中没有任何循环，所以时间复杂度为
O(1) - 因其中没有任何数组或矩阵，所以空间复杂度为
O(1)
LeetCode: 206.反转链表
题目描述
解题思路
解题步骤
Code
/**
* 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 = head;
let p2 = null;
while(p1){
const tem = p1.next; // 临时存储p1.next
p1.next = p2;
// console.log(p1.val, p2 && p2.val);
p2 = p1;
// p1 = p1.next;
p1 = tem;
}
return p2;
};
时间复杂度 空间复杂度分析
- 因其中有
while，所以时间复杂度为O(n) - 因其中没有任何数组或矩阵，所以空间复杂度为
O(1)
LeetCode: 002.两数相加 （遍历链表操作）
题目描述
解题思路
解题步骤
code
/**
* 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) {
const l3 = new ListNode(0); // 创建一个空链表
let p1 = l1; // 声明一个指针指向链表的头部
let p2 = l2; // 声明一个指针指向链表的头部
let p3 = l3; // 声明一个指针指向链表的头部
let carry = 0; // 声明十位
while(p1 || p2){
const v1 = p1 ? p1.val : 0; // 判断是否有值，有值则赋值给v1,否则为0
const v2 = p2 ? p2.val : 0; // 判断是否有值，有值则赋值给v1,否则为0
const val = v1 + v2 + carry;
carry = Math.floor( val / 10 ); // 将十位的数赋值给carry
p3.next = new ListNode( val % 10 ); // 将个位的数赋值给p3的下一个节点
if(p1) p1 = p1.next; // 若不为空则一直往下传递
if(p2) p2 = p2.next;
p3 = p3.next;
}
if(carry){ // 判断是否进1，满足条件追加
p3.next = new ListNode(carry);
}
return l3.next;
};
时间复杂度 空间复杂度分析
- 因其中有
while所以时间复杂度为O(n)其中n为两个链表l1,l2 中的较大值 - 因其中没数组，但有链表，长度为l1,l2 较长的，所以空间复杂度为
O(n)
LeetCode: 083. 删除排序链表中的重复元素 （遍历链表操作； 删除节点操作）
题目描述
解题思路
解题步骤
Code
/**
* 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 p = head; // 声明指针指向链表的头部
while(p && p.next){ // 当前指针和下一个指针有值的情况下执行
if(p.val === p.next.val){ // 当前值与下一个值相同时
p.next = p.next.next; // 删除下一个值
} else{ // 当下一个值没有重复值时
p = p.next; // 往下执行
}
}
return head;
};
时间复杂度 空间复杂度分析
- 因其中有
while所以时间复杂度为O(n) - 因其中没有额外存储线性增长的数组、矩阵、链表，所以空间复杂度为
O(1)
LeetCode: 141. 环形链表 （遍历链表操作）
题目描述
解题思路
- 快指针即： 一次多走几步
- 慢指针即： 一次走一步
解题步骤
code
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let p1 = head; // 声明指针指向链表头部
let p2 = head; // 声明指针指向链表头部
while(p1 && p2 && p2.next){ // 保证 p1,p2, p2.next有值的情况下执行下述操作，否则会报错
p1 = p1.next; // p1 指向下一节点
p2 = p2.next.next; // p2 指向下下节点
if(p1 === p2){ // 若两个指针相逢，则表示有环
return true;
}
}
return false;
};
时间复杂度 空间复杂度分析
- 因其中有
while所以时间复杂度为O(n) - 因其中没有额外存储线性增长的数组、矩阵、链表，所以空间复杂度为
O(1)
举一反三
追击问题
前端与链表： JS中的原型链
原型链定义
const obj = {};
const func = () => {};
const arr = [];
// 通过调试
// func.__proto__ === Function.prototype: true
// func.__proto__.__proto__ === Object.prototype: true
// arr.__proto__ === Array.prototype: true
// arr.__proto__.__proto__ === Object.prototype: true
原型链知识点
- A instanceof B 为 true 的原理
obj instanceof Object: true // 在obj变量的原型链上能够找到Object的原型对象
func instanceof Function: true // 任何函数，即是Function 的实例，也是Object的实例
func instanceof Object: true
arr instanceof Function: true
arr instanceof Object: true
- 沿着原型链往上找
const obj = {};
Object.prototype.x = 'x';
const func = () => {};
Function.prototype.y = 'y';
// WATCH
// obj.x = 'x'
// func.y = 'y'
// func.x = 'x'
面试题一
题目描述
简述instanceof 的原理，并用代码实现。
code
const instanceOf = (A, B) => {
let p = A; // 声明指针指向链表的头部
while(p){
// 需要执行的逻辑
if(p === B.prototype){
return true;
}
p = p.__proto__; // 循环遍历
}
return false;
};
验证结果
// WATCH验证
instanceOf(1, Number): true
instanceOf([], Array): true
面试题二
题目描述
题目分析
code
var foo = {},
F = function () {};
Object.prototype.a = 'value a';
Function.prototype.b = 'value b';
验证结果
foo.a: "value a"
foo.b: undefined
F.a: "value a"
F.b: "value 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];
});
// 当前沿着地址往下找，首先找到了b p:{c: 1} 最后找到了c 所以最后 p:1
总结
