前端算法：链表（力扣141、237题解法）
目录
一、链表
1.链表的基本概念
2.链表的种类
二、链表的基本操作
1.插入
2.删除
3.查找
4.遍历
5.单向链表实现实例
三、链表与数组的区别
1.数据插入
2.查找
3.大小
四、链表力扣实战
1.第141题环形链表
2.237题 删除链表中的节点
五、总结
一、链表
1.链表的基本概念
-
节点 (Node): 链表的基本组成部分，通常包含两部分：
- 数据部分 (value): 存储数据的值。
- 指针部分 (next): 指向链表中的下一个节点。
-
头指针 (head): 指向链表的第一个节点，如果链表为空，头指针通常为
null。 -
尾指针 (tail): 指向链表的最后一个节点，通常它的
next指针为null。
2.链表的种类
- 单向链表 : 每个节点只指向下一个节点。
- 双向链表 : 每个节点包含两个指针，分别指向前一个节点和后一个节点。
- 循环链表 : 最后一个节点的
next指针指向头节点，从而形成一个环。
二、链表的基本操作
1.插入
- 在链表的头部插入节点。
- 在链表的尾部插入节点。
- 在链表的指定位置插入节点。
代码：
// 在链表头部插入新节点
insertAtHead(value) {
const newNode = new Node(value);
newNode.next = this.head; // 新节点指向原头节点
this.head = newNode; // 更新头指针
this.size++;
}
// 在链表尾部插入新节点
insertAtTail(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode; // 如果链表为空，直接将头指针指向新节点
} else {
let current = this.head;
while (current.next) {
current = current.next; // 找到最后一个节点
}
current.next = newNode; // 将新节点添加到尾部
}
this.size++;
}
// 在指定位置插入新节点
insertAtPosition(value, position) {
if (position < 0 || position > this.size) {
throw new Error("Position out of bounds");
}
if (position === 0) {
this.insertAtHead(value); // 插入到头部
} else {
const newNode = new Node(value);
let current = this.head;
for (let i = 0; i < position - 1; i++) {
current = current.next; // 找到插入位置的前一个节点
}
newNode.next = current.next; // 新节点指向当前节点的下一个节点
current.next = newNode; // 当前节点指向新节点
this.size++;
}
}2.删除
- 删除链表的头节点。
- 删除链表的尾节点。
- 删除指定位置的节点。
代码：
// 删除链表的头节点
deleteHead() {
if (!this.head) return; // 如果链表为空，直接返回
this.head = this.head.next; // 将头指针指向下一个节点
this.size--;
}
// 删除链表的尾节点
deleteTail() {
if (!this.head) return; // 如果链表为空，直接返回
if (this.head.next === null) { // 只有一个节点的情况
this.head = null; // 直接将头指针设为 null
} else {
let current = this.head;
while (current.next && current.next.next) {
current = current.next; // 找到倒数第二个节点
}
current.next = null; // 将倒数第二个节点的 next 设为 null
}
this.size--;
}3.查找
- 查找链表中是否存在某个值。
4.遍历
- 遍历链表，访问每个节点的数据。
代码：
// 遍历链表并打印每个节点的值
traverse() {
let current = this.head;
while (current) {
console.log(current.value);
current = current.next; // 移动到下一个节点
}
}5.单向链表实现实例
class Node {
constructor(value) {
this.value = value; // 数据部分
this.next = null; // 指针部分
}
}
class SinglyLinkedList {
constructor() {
this.head = null; // 头指针
this.size = 0; // 链表大小
}
// 在链表头部插入新节点
insertAtHead(value) {
const newNode = new Node(value);
newNode.next = this.head; // 新节点指向原头节点
this.head = newNode; // 更新头指针
this.size++;
}
// 在链表尾部插入新节点
insertAtTail(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode; // 如果链表为空，直接将头指针指向新节点
} else {
let current = this.head;
while (current.next) {
current = current.next; // 找到最后一个节点
}
current.next = newNode; // 将新节点添加到尾部
}
this.size++;
}
// 在指定位置插入新节点
insertAtPosition(value, position) {
if (position < 0 || position > this.size) {
throw new Error("Position out of bounds");
}
if (position === 0) {
this.insertAtHead(value); // 插入到头部
} else {
const newNode = new Node(value);
let current = this.head;
for (let i = 0; i < position - 1; i++) {
current = current.next; // 找到插入位置的前一个节点
}
newNode.next = current.next; // 新节点指向当前节点的下一个节点
current.next = newNode; // 当前节点指向新节点
this.size++;
}
}
// 删除链表的头节点
deleteHead() {
if (!this.head) return; // 如果链表为空，直接返回
this.head = this.head.next; // 将头指针指向下一个节点
this.size--;
}
// 删除链表的尾节点
deleteTail() {
if (!this.head) return; // 如果链表为空，直接返回
if (this.head.next === null) { // 只有一个节点的情况
this.head = null; // 直接将头指针设为 null
} else {
let current = this.head;
while (current.next && current.next.next) {
current = current.next; // 找到倒数第二个节点
}
current.next = null; // 将倒数第二个节点的 next 设为 null
}
this.size--;
}
// 遍历链表并打印每个节点的值
traverse() {
let current = this.head;
while (current) {
console.log(current.value);
current = current.next; // 移动到下一个节点
}
}
// 获取链表的大小
getSize() {
return this.size;
}
}
const list = new SinglyLinkedList();
list.insertAtHead(10);
list.insertAtTail(20);
list.insertAtPosition(15, 1);
list.traverse(); // 输出: 10, 15, 20
list.deleteHead();
list.traverse(); // 输出: 15, 20
list.deleteTail();
list.traverse(); // 输出: 15
console.log("Size:", list.getSize()); // 输出: Size: 1
三、链表与数组的区别
1.数据插入
数组：如果在中间插入新的元素，其他元素会被重新计算。
链表：不会重新计算，说白了就是复制或者替换的一种。
2.查找
数组：通过下标进行查找。
链表：每次查找都需要从头部开始。
3.大小
链表：可以根据需求动态进行扩展。
数组：需要预先定义大小
四、链表力扣实战
1.第141题环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
解题思路：
本题说给一个头节点head，如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
那么首先定义两个节点，t和s,将head头节点赋值给它俩。进行链表遍历，令s=s的下一个节点，t为t的下一个节点，判断s和t是否===,相同返回true，全部遍历完没有结果则返回false
代码如下：
var hasCycle = function(head) {
let t = head, s = head
while(t !== null && t.next !== null){
s = s.next
t = t.next.next
if( s === t){
return true
}
}
return false
};2.237题 删除链表中的节点
有一个单链表的 head，我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
node前面的所有值顺序相同。node后面的所有值顺序相同。
自定义测试：
- 对于输入，你应该提供整个链表
head和要给出的节点node。node不应该是链表的最后一个节点，而应该是链表中的一个实际节点。 - 我们将构建链表，并将节点传递给你的函数。
- 输出将是调用你函数后的整个链表。
输入：head = [4,5,1,9], node = 5
输出：[4,1,9] 解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9
解题思路：此题含义为给定一个链表head和要删除的节点node，输出删除节点后的链表，那么只需要将node节点跳过即可解出本题，也就是让node的val值和next等于它下一个val值和next。
代码如下：
var deleteNode = function(node) {
node.val = node.next.val
node.next = node.next.next
};五、总结
链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组相比，链表具有灵活的大小和高效的插入、删除操作，但在随机访问方面较慢。常见的链表类型包括单向链表、双向链表和循环链表。