当前位置：首页 > news >正文

算法刷题记录——LeetCode篇(2.5) [第141~150题](持续更新)

news 来源：原创 2025/8/28 7:07:51

更新时间：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^5
pos 为 -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^5
pos 的值为 -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 <= 3000
0 <= key <= 10000
0 <= 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后面，返回合并后的新tailprivate 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 ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

141. 环形链表

方法一：快慢指针（Floyd判圈算法）

方法二：哈希表

复杂度分析

142. 环形链表 II

方法一：快慢指针（Floyd判圈算法）

方法二：哈希表

复杂度分析：

146. LRU 缓存

方法：哈希表结合双向链表

复杂度分析

148. 排序链表

方法一：归并排序（递归）

复杂度分析

方法二：归并排序（迭代）

复杂度分析

对比总结

相关文章：