链表
链表和数组一样是有多个元素组成的列表;
不同的是链表元素存储不连续,用next指针连接在一起;
![图片来源于网络](https://img-blog.csdnimg.cn/6c169613031546e1a594421ad79b6f5b.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTAxMDA3,size_16,color_FFFFFF,t_70)
链表的特点
- 插入、删除不需要移动元素;
- 不必事先分配存储空间;
- 所需空间与长度成线性正比;
- 不访问指定元素;
链表和数组的区别
数组:增删非首尾元素时,后面的元素需要移动。
链表:增删非首尾元素时,不需要移动元素,修改next指向即可。
JS模拟链表
虽然JavaScript中没有链表,但是我们可以用对象 来实现链表的功能。
// 用对象模拟链表
const a = { value: 'a' };
const b = { value: 'b' };
const c = { value: 'c' };
const d = { value: 'd' };
const e = { value: 'e' };
// 用next属性将对象连起来
a.next = b;
b.next = c;
c.next = d;
d.next = e;
![在这里插入图片描述](https://img-blog.csdnimg.cn/d6aca06c1b044cbe89cd9239d3199001.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTAxMDA3,size_16,color_FFFFFF,t_70)
遍历链表
// 定义指针p
let p = a;
while(p){
console.log(p.value);
p = p.next;
}
![在这里插入图片描述](https://img-blog.csdnimg.cn/f90d13d894cc4fe1ad8c24d028af44f7.png)
插入节点
将节点f 查到节点a 和 节点b之间;
const f = { value: 'f' };
//修改next指向
a.next = f;
f.next = b;
![在这里插入图片描述](https://img-blog.csdnimg.cn/680aa25a2a3e42f8aec05a9e2e443c07.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTAxMDA3,size_16,color_FFFFFF,t_70)
删除节点
修改next指向,删除节点f;
a.next = b;
![在这里插入图片描述](https://img-blog.csdnimg.cn/47126856417346f280daa2faac1bd0a8.png)
链表应用
删除链表中的节点(leetcode:237)
![在这里插入图片描述](https://img-blog.csdnimg.cn/79394ec2e4e04066a3d830b284143744.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTAxMDA3,size_16,color_FFFFFF,t_70)
思路
将下一个节点的值赋值给当前节点;
删除下一个节点;
代码
var deleteNode = function(node) {
// 将下一个节点值赋值给当前节点
node.val = node.next.val;
// 删除下一个节点
node.next = node.next.next;
};
![在这里插入图片描述](https://img-blog.csdnimg.cn/c68e54ac706c4545a1b40f68fda57968.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTAxMDA3,size_16,color_FFFFFF,t_70)
反转链表(leetcode:206)
![在这里插入图片描述](https://img-blog.csdnimg.cn/506ccccac9a049a4acb98b208ce252d0.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTAxMDA3,size_16,color_FFFFFF,t_70)
思路
使用双指针一前一后遍历链表;
然后反转双指针;
代码
var reverseList = function(head) {
// 定义双指针p1、p2 p1指向头节点,p2指向null(头节点前一个节点)
let p1 = head;
let p2 = null;
//p1指向null时遍历完链表
while(p1){
const t = p1.next;
// 反转链表
p1.next = p2;
// 遍历链表
p2 = p1;
p1 = t;
}
return p2;
};
![在这里插入图片描述](https://img-blog.csdnimg.cn/a488507f0dca42269a8dfd269867b134.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTAxMDA3,size_16,color_FFFFFF,t_70)