更新时间：2025-04-04
- 算法题解目录汇总：算法刷题记录——题解目录汇总
- 技术博客总目录：计算机技术系列博客——目录页
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]-10^5 <= Node.val <= 10^5pos 为 -1 或者链表中的一个有效索引
进阶：
你能用 O(1)（常量）内存解决此问题吗？
方法一：快慢指针（Floyd判圈算法）
使用两个指针，一个快指针每次移动两步，一个慢指针每次移动一步。如果链表中有环，快指针最终会追上慢指针；如果快指针到达链表末尾（遇到null），则说明链表无环。
- 初始化快慢指针都指向头节点。
- 快指针每次移动两步，慢指针每次移动一步。
- 如果快慢指针相遇，说明有环；若快指针遍历到链表末尾，说明无环。
代码实现(Java)：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
方法二：哈希表
遍历链表，用哈希表记录已访问过的节点。如果遇到重复节点，说明存在环；否则遍历完成无环。
- 创建哈希表存储访问过的节点。
- 遍历链表，检查当前节点是否已存在于哈希表中。
- 存在则返回true，否则将节点加入哈希表。
- 遍历结束返回false。
代码实现(Java)：
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
while (head != null) {
if (visited.contains(head)) {
return true;
}
visited.add(head);
head = head.next;
}
return false;
}
}
复杂度分析
- 快慢指针法：时间复杂度
O(n)，空间复杂度O(1)。通过双指针的追赶机制高效检测环。 - 哈希表法：时间复杂度
O(n)，空间复杂度O(n)。利用哈希表的唯一性记录访问过的节点，实现简单但空间占用较高。
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 10^4] 内-10^5 <= Node.val <= 10^5pos 的值为 -1 或者链表中的一个有效索引
方法一：快慢指针（Floyd判圈算法）
判断是否有环：快慢指针相遇说明有环；寻找环入口：相遇后，将其中一个指针重置到头节点，两指针以相同速度前进，再次相遇的节点即为环入口。
- 快指针每次走两步，慢指针每次走一步，找到相遇点。
- 初始化两个指针分别从头节点和相遇点出发，同步移动直至相遇。
代码实现(Java)：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
boolean hasCycle = false;
// 判断是否存在环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}
if (!hasCycle) return null;
// 寻找环入口
ListNode ptr1 = head, ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return ptr1;
}
}
方法二：哈希表
遍历链表并记录访问过的节点，第一个重复的节点即为环入口。
- 使用哈希表存储已访问的节点。
- 遍历链表，若当前节点已存在于哈希表，则返回该节点；否则继续遍历。
代码实现(Java)：
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode node = head;
while (node != null) {
if (visited.contains(node)) {
return node;
}
visited.add(node);
node = node.next;
}
return null;
}
}
复杂度分析：
- 快慢指针法：时间复杂度
O(n)，空间复杂度O(1)。通过数学推导找到环入口，高效且节省内存。 - 哈希表法：时间复杂度
O(n)，空间复杂度O(n)。实现简单，但需要额外空间存储节点，适用于空间不敏感的场景。
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) 的平均时间复杂度运行。
示例：
输入:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 10^5最多调用 2*10^5 次 get 和 put
方法：哈希表结合双向链表
LRU缓存机制要求快速定位元素是否存在，并维护元素的访问顺序。利用哈希表实现O(1)时间的查找，双向链表维护访问顺序，最近访问的节点置于链表头部，尾部则为最久未使用的节点。
- 数据结构设计：
- 双向链表节点包含键、值、前驱和后继指针。
- 哈希表存储键到链表节点的映射。
- 初始化：
- 创建虚拟头尾节点，形成空链表。
- get操作：
- 若键存在，将对应节点移至链表头部并返回值；否则返回-1。
- put操作：
- 若键存在，更新值并将节点移至头部。
- 若不存在，创建新节点并添加到头部及哈希表中。若容量超限，删除尾部节点并更新哈希表。
- 代码实现关键点：
- 双向链表操作：通过虚拟头尾节点简化链表操作，确保插入和删除的指针调整正确。
- 哈希表维护：哈希表与链表同步更新，保证快速访问和空间管理。
- LRU策略实现：通过链表顺序维护访问时间，头部为最新，尾部为最旧，容量超限时删除尾部节点。
代码实现(Java)：
class LRUCache {
class Node {
int key;
int value;
Node prev;
Node next;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, Node> cache;
private int capacity;
private int size;
private Node dummyHead;
private Node dummyTail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
cache = new HashMap<>();
dummyHead = new Node();
dummyTail = new Node();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
} else {
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);
size++;
if (size > capacity) {
Node tail = removeTail();
cache.remove(tail.key);
size--;
}
}
}
private void addToHead(Node node) {
node.prev = dummyHead;
node.next = dummyHead.next;
dummyHead.next.prev = node;
dummyHead.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private Node removeTail() {
Node tail = dummyTail.prev;
removeNode(tail);
return tail;
}
}
复杂度分析
- 时间复杂度：
get和put操作均为O(1)。 - 空间复杂度：
O(capacity)，用于存储哈希表和链表节点。
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5*10^4] 内-10^5 <= Node.val <= 10^5
方法一：归并排序（递归）
采用归并排序算法，通过分治策略将链表不断分割成子链表，直到每个子链表只有一个节点，然后逐步合并有序链表。关键点在于正确分割链表和高效合并两个有序链表。
- 递归终止条件：链表为空或只有一个节点时直接返回。
- 寻找中间节点：使用快慢指针法找到链表中点，将链表分为左右两部分。
- 递归排序：分别对左右子链表进行递归排序。
- 合并有序链表：将两个已排序的子链表合并成一个有序链表。
代码实现(Java)：
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 使用快慢指针找到中间节点
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null; // 将链表断开为两部分
// 递归排序左右两部分
ListNode left = sortList(head);
ListNode right = sortList(slow);
// 合并有序链表
return merge(left, right);
}
// 合并两个有序链表
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
复杂度分析
- 时间复杂度：
O(n log n)，归并排序的典型时间复杂度。 - 空间复杂度：
O(log n)，递归调用栈的深度。
方法二：归并排序（迭代）
通过迭代方式实现归并排序，避免递归带来的栈空间开销。每次将链表分成固定大小的块，逐步合并相邻块，直到整个链表有序。
- 计算链表长度：确定需要合并的次数。
- 分块合并：每次将链表分割成大小为
step的块，合并相邻块。 - 调整步长：每次合并后步长翻倍，直到步长超过链表长度。
代码实现(Java)：
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 计算链表长度
int len = 0;
ListNode curr = head;
while (curr != null) {
len++;
curr = curr.next;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
// 迭代合并，步长从1开始倍增
for (int step = 1; step < len; step *= 2) {
ListNode tail = dummy;
ListNode left = dummy.next;
while (left != null) {
ListNode right = split(left, step);
ListNode next = split(right, step);
tail = merge(left, right, tail);
left = next;
}
}
return dummy.next;
}
// 分割链表，返回分割后的右半部分头节点
private ListNode split(ListNode head, int step) {
if (head == null) return null;
for (int i = 1; head.next != null && i < step; i++) {
head = head.next;
}
ListNode right = head.next;
head.next = null;
return right;
}
// 合并两个链表，并连接到tail后面，返回合并后的新tail
private ListNode merge(ListNode l1, ListNode l2, ListNode tail) {
ListNode curr = tail;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
while (curr.next != null) curr = curr.next;
return curr;
}
}
复杂度分析
- 时间复杂度：
O(n log n)，与递归方法相同。 - 空间复杂度：
O(1)，仅使用常量额外空间。
对比总结
| 方法 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 递归归并 | 代码简洁，逻辑清晰 | 栈空间O(log n) |
常规场景，链表较短 |
| 迭代归并 | 无栈溢出风险，空间更优 | 实现较复杂，指针操作多 | 链表较长或空间敏感场景 |
声明
- 本文版权归
CSDN用户Allen Wurlitzer所有，遵循CC-BY-SA协议发布，转载请注明出处。- 本文题目来源
力扣-LeetCode，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。