链表小记

nancy Jane2024-03-202024-03-20

知识点小记

一.快慢链表

快慢指针是一种常用的算法技巧，广泛应用于链表和数组中，解决如环形链表检测、链表中点查找、判断链表是否有环等问题。它涉及两个指针，分别称为“快指针”和“慢指针”。快指针的移动速度是慢指针的两倍，即每次循环中，慢指针移动一步，快指针移动两步。这种差速移动可以帮助解决一系列问题，以下是一些常见的应用示例：

为什么快指针的移动速度是慢指针两倍？想象一下一个环形跑道，跑的快的人始终会和跑得慢的人相遇，但如果将快指针一次移动两步或以上，就会出现错过慢指针的情况，不利于应用于链表判断

1检测链表中的环

快慢指针可以用来检测链表是否有环。具体方法是，两个指针同时从链表的头节点出发，快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，那么快指针最终会追上慢指针（两者相遇），这说明链表有环；如果链表中没有环，快指针会先到达链表的末尾。

class ListNode {
    constructor(value = 0, next = null) {
        this.value = value;
        this.next = next;
    }
}

function hasCycle(head) {
    if (head === null) {
        return false;
    }

    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next; // 慢指针移动一步
        fast = fast.next.next; // 快指针移动两步

        if (slow === fast) {
            // 如果在某个点快指针追上了慢指针，则表示链表中存在环
            return true;
        }
    }

    // 如果快指针到达链表末尾，则表示链表中不存在环
    return false;
}

2查找链表的中点

使用快慢指针查找链表的中点时，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针正好在链表的中间位置。如果链表的长度是奇数，慢指针指向中间节点；如果长度是偶数，慢指针指向中间两个节点的第一个。

3查找链表中倒数第n个节点

首先，让快指针移动n步，然后快慢指针同时开始移动，每次各移动一步。当快指针到达链表末尾时，慢指针所在的位置就是倒数第n个节点。

二.哈希表

1定义

哈希表（Hash Table），也被称为散列表，是一种用于存储键值对的数据结构。哈希函数的作用是将输入（通常是一个键）转换成一个固定范围内的整数值，这个整数值就作为数组（哈希表背后的数据结构）的索引。这样，通过键就能直接计算出值存储的位置，从而极大提高查找速度。

哈希表的核心组成部分包括：

哈希函数：负责将输入（键）映射到一个有限的索引范围（例如，数组的索引）。
数组：用于存储数据的连续内存空间。
冲突解决策略：由于哈希函数可能将不同的输入映射到同一个输出（这称为“冲突”），所以需要一种机制来处理这些冲突。常见的策略包括链表法（将冲突的元素存储在链表中）和开放寻址法（寻找数组中的另一个空槽位）。

哈希表的性能很大程度上依赖于哈希函数的选择和冲突解决策略的效率。一个好的哈希函数会均匀地分布键，减少冲突的可能性，从而提高整个哈希表的性能。

在最理想的情况下，**哈希表的查找、插入和删除操作的时间复杂度为O(1)**。然而，在最坏的情况下，比如当所有的键都映射到同一个位置时，这些操作的时间复杂度会退化为O(n)，其中n是哈希表中元素的数量。因此，设计一个高效的哈希函数和选择合适的冲突解决策略对于实现一个高效的哈希表至关重要。

2小题

哈希表判断单向链表中是否存在环

function hasCycle(head) {
    const visited = new Set(); // 创建一个哈希表来存储访问过的节点

    let current = head; // 从头节点开始遍历链表
    while (current !== null) { // 遍历直到链表结束
        if (visited.has(current)) { // 如果当前节点已经存在于哈希表中，则表示链表存在环
            return true; // 返回true表示存在环
        }
        visited.add(current); // 将当前节点添加到哈希表中
        current = current.next; // 移动到下一个节点
    }

    return false; // 如果遍历完链表没有发现环，则返回false
}

3实现

大多数现代编程语言中都已经内置了哈希表的实现，如JavaScript的Map和Set，Python的dict，Java的HashMap等

Map 和 Set 是现代JavaScript中提供的两种集合类型，它们各自有一系列的方法用于操作集合中的数据。下面列出了这些方法中的一些常用的。

关于map和set，值得思考的地方有很多，很多优秀的前人写的文章都非常详细且易于理解，非常帮助理解。

https://zhuanlan.zhihu.com/p/523850774

4.Map 的常用方法

new Map(): 创建一个新的 Map 对象。
set(key, value): 向 Map 添加一个新的键值对。如果键已经存在，则更新对应的值。
get(key): 根据键来获取对应的值。如果键不存在，则返回 undefined。
has(key): 检查 Map 中是否存在指定的键。返回一个布尔值。
delete(key): 根据键来删除对应的键值对。成功删除返回 true，否则返回 false。
clear(): 清除 Map 中的所有键值对。
size: 一个属性，返回 Map 中键值对的数量。
keys(): 返回一个新的 Iterator 对象，它按插入顺序包含了 Map 对象中每个元素的键。
values(): 返回一个新的 Iterator 对象，它按插入顺序包含了 Map 对象中每个元素的值。
entries(): 返回一个新的 Iterator 对象，它按插入顺序包含了 Map 对象中每个元素的 [key, value] 数组。
forEach(callbackFn[, thisArg]): 按插入顺序，为 Map 对象中的每个键值对调用一次提供的回调函数。

5.Set 的常用方法

new Set(): 创建一个新的 Set 对象。
add(value): 向 Set 添加一个新的元素。如果该元素已存在，则 Set 不会改变。
delete(value): 从 Set 中删除指定的元素。成功删除返回 true，否则返回 false。
has(value): 检查 Set 中是否存在指定的元素。返回一个布尔值。
clear(): 清除 Set 中的所有元素。
size: 一个属性，返回 Set 中元素的数量。
values() / keys(): Set 没有键的概念，values() 和 keys() 方法返回一个新的 Iterator 对象，它包含了 Set 中的每个元素。由于历史原因，keys() 方法的行为与 values() 方法相同。
entries(): 返回一个新的 Iterator 对象，它包含了 Set 中每个元素的 [value, value] 数组。
forEach(callbackFn[, thisArg]): 对 Set 对象中的每个元素执行一次提供的回调函数。

这些方法为 Map 和 Set 提供了灵活的操作方式，可以用来执行各种集合操作，如添加、删除、查找和遍历等。

6.补充

https://blog.csdn.net/jianghao233/article/details/103772274