剑指offer21-31链表

剑指 Offer II 021. 删除链表的倒数第 n 个结点

链表操作，一种常用的技巧是添加一个哑节点（dummy node）
本题是删除倒数第n个结点

方法一：计算链表长度

第一遍获取链表长度
第二遍删除

方法二：栈

先入栈，然后出栈时查是第几个

方法三：双指针

左指针比右指针超前n个元素，当右指针到达末尾（空），左指针正好为那个元素

剑指 Offer II 022. 链表中环的入口节点

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

方法一：哈希表

定义一个哈希表，用于存放已经访问的节点，

方法二：快慢指针

设置fast和slow指针，fast每次走两步，slow每次走一步。

为什么两个指针会相遇？
因为运动是相对的。
将慢指针视作参照系，考虑快指针相对于慢指针的速度，如果慢指针每次走一步，快指针每次走两步，那么等于慢指针不变，快指针相对于慢指针每次走一步。
那么问题转换为一个指针一步步走，假如list有环的话一定能回环的原点

fast一定比slow多走了k步，这多走的k步其实就是fast指针在环里转圈圈，所以k的值就是环长度的「整数倍」，为什么是整数倍?

假设在蓝点相遇，两者同时走了a的距离，然后在蓝点相遇了，快的减去慢的一定是环长度的整数倍
f为快指针走的路程，s是慢指针走的路程，由下面前两个得出第三个式子

剑指 Offer II 023. 两个链表的第一个重合节点

给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

方法一：哈希表

方法二：双指针

思路：

简单来说，如果pA指针到了末尾，让它去B的开头，如果pB指针到了末尾，让它去A的开头，这样一定会同时到达相交节点
下面证明下：

剑指 Offer II 024. 反转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

方法一：正常迭代

方法二：递归

不用看了

剑指 Offer II 025. 链表中的两数相加

给定两个 非空链表 11和 12 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

方法一：栈

将两列元素压到栈里，然后开始每次谈两个，让他们相加，如果有一个栈里为空，那么设置其为0，然后需要注意进位，将进位想加

附加题：反转链表

方法一：迭代

方法二：递归

剑指 Offer II 026. 重排链表

方法一：利用线性表

利用线性表存储链表的各个节点，然后利用线性表可以下标访问的特点然后直接通过下标访问修改它的next值。

寻找链表中间节点

快慢指针，快指针每次走两步，慢指针每次走一步，当快指针不能移动了（下一个为空，或者下下个为空）此时的慢指针指向的就为中间节点

偶数位置

奇数位置

合并链表

假设两个链表元素相等，或者第一个链表比第二个链表多一个元素

方法二：

目标链表是原链表的左半端和反转后的右半端合并后的结果

所以任务变为
1、找到原链表的中点，这里用上面那个寻找链表中间节点方法
2、将原链表的右半端反转，这里用上面题的迭代
3、将原链表的两端合并

剑指 Offer II 027. 回文链表

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

方法一：辅助空间

1、将值复制到数组列表中
2、使用双指针法判断是否为回文

方法二 ：递归

递归是最后一个运行的，用一个全局指针指向元素，将这两个对比
递归过程建议看图解
图解

方法三：特点

剑指 Offer II 028. 展平多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

方法

插入

删除

删除元素先判断字典里存在吗
如果存在，那么将要删除元素，将被删除元素和最后一个元素交换，这样就避免移动很多元素了

得到任意值

 srand((unsigned)time(NULL));
 int randomIndex = rand() % nums.size();
 return nums[randomIndex];
1
2
3

剑指 Offer II 031. 最近最少使用缓存

解法

缓存用双向链表存储
而快速得到用一个unordered_map来实现，这个map存储值和节点（这个节点就是链表上的节点，也就是通过key能快速定位到这个节点）

得到值
1、在map中根据key确定是否存在
2、如果存在，那么返回节点对应的值，并且处理影响也即移到头部
放值
分为key存在和不存在

当key存在，根据哈希表定位，修改它的值，并移动到头部
当key不存在
创建一个新的节点
将这个节点加入哈希表
将这个节点添加到链表的头部
更新链表的总数
如果链表的长度超过了容量，那么删除尾部元素，这个删除需要返回被删除的节点，然后在哈希表中删除这个节点，修改链表的总数

定义几个函数
注意有俩哑节点 head和tail,head->next是第一个节点，tail->prev是倒数第一个节点

addToHead 将节点加到头部
对node俩指针初始化，node前指针指向head，后指针指向第一个节点
修改原第一个节点前指针，修改哑节点的后指针
removeNode 删除一个节点
修改当前节点的前一个节点的后指针
修改当前节点的后一个节点的前指针
moveToHead 移动到开头
调用删除节点函数 removeNode
调用添加节点函数 addToHead
removeTail 删除尾节点
找到尾节点
调用删除节点函数
将被删除节点返回

代码

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity) : capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77