单向链表排序（单向链表快速排序）

通常会使用dummyHead即头结点来操作链表以规避额外判断首结点是否为空的问题。

可以使用dummyHead与dummyTail满足

以实现循环双链表的功能。

#19 删除链表的倒数第N个结点（快慢指针）： 给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

#141 环形链表（快慢指针）： 给你一个链表的头节点head，判断链表中是否有环。

#206 回文链表（快慢指针+翻转链表）： 给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。

#25.K个一组翻转链表（快慢指针+翻转链表）： 给你链表的头节点head，每k个节点一组进行翻转，请你返回修改后的链表。

k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

#61. 旋转链表（合并成环再截断）： 给你一个链表的头节点head，旋转链表，将链表每个节点向右移动k个位置。

#146 LRU 缓存（循环双链表）： 请你设计并实现一个满足LRU（最近最少使用）缓存约束的数据结构。

实现LRUCache类：

LRUCache(int capacity)：以正整数作为容量capacity初始化 LRU 缓存

int get(int key)：如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。

void put(int key, int value)：如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。

函数get和put必须以O(1)的平均时间复杂度运行。

#460 LFU 缓存（循环双链表）： 请你为LFU（最不经常使用）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity)：用数据结构的容量capacity初始化对象

int get(int key)：如果键key存在于缓存中，则获取键的值，否则返回 -1 。

void put(int key, int value)：如果键key已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量capacity时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个使用计数器。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为1(由于put操作)。对缓存中的键执行get或put操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

这题我暂时没有做出一个非常好的解法，成功AC的解法也是利用了put和ge方法最多调用2*10^5次。大体思路是使用两个哈希表key-node表和frequency-node表来维护。为了实现使用计数器平局时按LRU调度，此处用了双循环链表来记录所有同样frequency的结点。这么做会遇到一个没办法通过O（1）时间复杂度解决的问题，我无法确定frequency-node表中最小不为空的node的frequency是多少，因此在进行put更新和get操作时我就需要在使操作的结点频率加1的同时确定最小值。

#155 最小栈（双链表）： 设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

实现MinStack类:

MinStack()：初始化堆栈对象。

void push(int val) ：将元素val推入堆栈。

void pop() ：删除堆栈顶部的元素。

int top() ：获取堆栈顶部的元素。

int getMin() ：获取堆栈中的最小元素。

本文使用BiliBili-Markdown油猴脚本实现在b站专栏投稿中使用Markdown语法。

~~为什么是上是因为我栈的题目还没全做完，先做了一部分树的，下次再写吧！饿死了，16个小时没吃东西了，该出去吃早饭了。~~

作者：从100ms到3ms的Citatsu

日期：2023.9.29

单向链表排序（单向链表 快速排序）

相关推荐

单向链表排序（单向链表快速排序）