LeetCode 热题 100 | 链表（下）

目录

1  148. 排序链表

2  23. 合并 K 个升序链表

3  146. LRU 缓存

3.1  解题思路

3.2  详细过程

3.3  完整代码

---

菜鸟做题第三周，语言是 C++

1  148. 排序链表

解题思路：

1. 遍历链表，把每个节点的 val 都存入数组中
2. 用 sort 函数对数组进行排序
3. 遍历链表，更新每个节点的 val

class Solution {
public:ListNode* sortList(ListNode* head) {ListNode * p = head;vector<int> vals;while (p) {vals.push_back(p->val);p = p->next;}sort(vals.begin(), vals.end());p = head;int i = 0;while (p) {p->val = vals[i];p = p->next;++i;}return head;}
};

2  23. 合并 K 个升序链表

解题思路：

1. 遍历所有链表，把每个节点的 val 都存入数组中
2. 用 sort 函数对数组进行排序
3. 构造新的链表，并放入数组中的值

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {vector<int> vals;int n = lists.size();if (n == 0) return nullptr;for (int i = 0; i < n; ++i) {ListNode * p = lists[i];while (p) {vals.push_back(p->val);p = p->next;}}sort(vals.begin(), vals.end());ListNode * dummy = new ListNode(0);ListNode * p = dummy;for (auto &val:vals) {ListNode * t = new ListNode(val);p->next = t;p = t;}return dummy->next;}
};

3  146. LRU 缓存

3.1  解题思路

• 构造双向链表，用于表示某节点最近是否被使用
• 构造哈希表，用于快速定位节点位置

Q：如何表示某节点最近是否被访问？

A：在我的解法中，将最近被使用的节点链在链表尾部。由此，越靠近头部的节点越少被使用。

Q：什么叫被使用？

A：被使用包含两种：最新被插入到链表中的节点、最新被访问的节点。

Q：为什么一定要构造双向链表？

A：哈希表中存储的是节点的地址，帮助我们快速定位。但是定位只能定位到节点本身，而不能定位到节点的前一个节点，因此使用单向链表将无法完成节点的删除。

3.2  详细过程

① 定义双向链表结构体

struct DListNode {int key, value;DListNode * prev, * next;DListNode() : key(0), value(0), prev(nullptr), next(nullptr) {}DListNode(int x, int y) : key(x), value(y), prev(nullptr), next(nullptr) {}
};

照抄力扣定义的结构体即可，只不过多了一个 prev 前向指针。

② 定义变量

int cap = 0, size = 0;
unordered_map<int, DListNode *> hashtable;
DListNode * head, * tail;

• cap 表示缓存的容量，size 表示缓存目前被占用的量
• hashtable 的键是节点的 key，值是节点的地址 DListNode *
• head 和 tail 是虚拟节点，辅助节点的插入和删除

③ 定义函数

void addToTail(int key, int value) {DListNode * node = new DListNode(key, value);hashtable[key] = node;node->next = tail;node->prev = tail->prev;tail->prev->next = node;tail->prev = node;++size;
}void moveToTail(int key) {DListNode * node = hashtable[key];node->prev->next = node->next;node->next->prev = node->prev;--size;addToTail(key, hashtable[key]->value);
}void delHeadNode() {DListNode * node = head->next;node->next->prev = head;head->next = node->next;delete node;
}

• addToTail：是指在链尾插入新的节点
• moveToTail：是指将最近使用到的节点删除，再插入到链尾
• delHeadNode：是指缓存空间不够时，删除头节点

由于在我的解法中 “越靠近头部的节点越少被使用”，所以每次被替换掉的是头节点。

3.3  完整代码

class LRUCache {
public:struct DListNode {int key, value;DListNode * prev, * next;DListNode() : key(0), value(0), prev(nullptr), next(nullptr) {}DListNode(int x, int y) : key(x), value(y), prev(nullptr), next(nullptr) {}};int cap = 0, size = 0;unordered_map<int, DListNode *> hashtable;DListNode * head, * tail;LRUCache(int capacity) {cap = capacity;head = new DListNode();tail = new DListNode();head->next = tail;tail->prev = head;}int get(int key) {if (hashtable.count(key)) {moveToTail(key);return hashtable[key]->value;}return -1;}void put(int key, int value) {if (hashtable.count(key)) {hashtable[key]->value = value;moveToTail(key);} else if (!hashtable.count(key)) {if (size < cap) {addToTail(key, value);} else if (size >= cap) {hashtable.erase(head->next->key);delHeadNode();addToTail(key, value);}}}void addToTail(int key, int value) {DListNode * node = new DListNode(key, value);hashtable[key] = node;node->next = tail;node->prev = tail->prev;tail->prev->next = node;tail->prev = node;++size;}void moveToTail(int key) {DListNode * node = hashtable[key];node->prev->next = node->next;node->next->prev = node->prev;--size;addToTail(key, hashtable[key]->value);}void delHeadNode() {DListNode * node = head->next;node->next->prev = head;head->next = node->next;delete node;}
};