LeetCode热题100（Java）（7）链表（下）

本章包括的题目有24. 两两交换链表中的节点 - 力扣LeetCode25. K 个一组翻转链表 - 力扣LeetCode138. 随机链表的复制 - 力扣LeetCode148. 排序链表 - 力扣LeetCode23. 合并 K 个升序链表 - 力扣LeetCode146. LRU 缓存 - 力扣LeetCode1.两两交换链表中的节点思路解析这道题的难点在于两两交换时指针容易丢失尤其是头节点也会参与交换直接操作很容易出错。代码采用了一个比较稳妥的策略先把每一对中靠前的节点按顺序存进数组把链表的动态结构拍平成静态的索引关系后续所有指针修改都基于数组下标进行避免了边遍历边改指针带来的混乱。具体来说第一轮遍历只收集每对的起始节点第二轮遍历则根据数组中的位置关系统一处理交换和拼接当前对的第二个节点指向第一个节点完成内部交换而第一个节点的 next 则根据下一对是否存在来决定接谁——如果还有下一对就接下一对的第二个节点即arr[i1].next否则接下一对的第一个节点或置空。这样无论链表长度是奇数还是偶数逻辑都是统一的不需要为边界情况写额外分支。最后返回预先保存的原第二个节点作为新头因为头节点一定参与了第一次交换这个值就是最终结果。代码实现class Solution { public ListNode swapPairs(ListNode head) { ListNode cur head; if(head null) return null; ListNode nex head.next; if(nex null) return head; ArrayListListNode arr new ArrayList(); while(cur ! null){ arr.add(cur); if(cur.next ! null) cur cur.next.next; else break; } for(int i 0;i arr.size();i){ if(arr.get(i).next ! null){ arr.get(i).next.next arr.get(i); if(i 1 arr.size()){ if(arr.get(i1).next ! null) arr.get(i).next arr.get(i1).next; else arr.get(i).next arr.get(i1); }else arr.get(i).next null; } } return nex; } }时间复杂度On空间复杂度On2.K 个一组翻转链表思路解析这道题的核心难点在于反转操作不可逆必须先确认当前分组恰好有 k 个节点才能执行否则不足 k 个的尾部需要保持原序。因此我将验证分组长度与执行反转解耦为两个独立步骤避免反转后发现长度不足而无法回退的问题。具体实现上每轮循环首先让 curTail 向前移动 k-1 步进行探测。若中途遇到 null说明剩余节点不足 k 个此时直接返回首次记录的头节点 firstTail因为已处理部分的头不会再改变。仅当 curTail 有效时才将 curTail.next 置空把当前 k 个节点从主链上切离并调用 swapList 完成反转。该函数职责单一仅负责将传入链表头尾颠倒并返回新头即原尾不涉及外部上下文。反转完成后原头节点变为新尾 newTail需将其与后续分组衔接。下一分组的起始节点为 nextHead但同样需要先验证其长度是否达到 k。通过让 nextTail 再走 k-1 步探测若探测失败则将 newTail 直接接上 nextHead保持原始顺序并返回 firstTail若探测成功则将 newTail 接至 nextTail并更新 curHead 与 curTail 进入下一轮迭代。这种设计使主逻辑聚焦于探测→切断→反转→衔接的流程控制反转细节被封装在独立函数中降低了耦合度。空间上仅使用常数个指针变量为 O(1) 原地操作时间上每个节点最多被访问两次探测一次、反转一次总体复杂度 O(n)在保证正确性的前提下兼顾了代码的清晰度与可维护性。代码实现class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode curHead head; ListNode curTail head; for (int i 1; i k; i) { curTail curTail.next; if(curTail null) return head; } ListNode firstTail curTail; while(true){ if(curTail null)return firstTail; ListNode nextHead curTail.next; curTail.next null; //断开和后面的连接 ListNode newTail swapList(curHead); ListNode nextTail nextHead; if(nextTail null) { newTail.next nextHead; return firstTail; } //寻找下一个头和尾 for (int i 1; i k; i) { nextTail nextTail.next; if(nextTail null) { newTail.next nextHead; return firstTail; } } newTail.next nextTail; curTail nextTail; curHead nextHead; } } //反转链表的函数 private ListNode swapList(ListNode head){ if(head null || head.next null) return head; ListNode pre null; ListNode cur head; ListNode nex cur.next; while(cur ! null){ cur.next pre; pre cur; cur nex; if(nex ! null)nex nex.next; } return head; } }时间复杂度On空间复杂度O13.随机链表的复制思路解析这道题的难点在于 random 指针可能指向链表中任意节点甚至为 null若边创建节点边设置指针很容易遇到目标节点尚未创建的情况。因此我采用两遍遍历的策略将节点创建与指针连接彻底分离确保第二遍设置指针时所有新节点都已存在。第一遍遍历仅负责建立原节点到新节点的映射关系。遍历原链表对每个节点创建一个值相同的新节点并以原节点为键、新节点为值存入 HashMap。此阶段不设置任何指针只保证每个原节点都有对应的新节点副本。第二遍遍历专注于指针的赋值。再次遍历原链表对每个原节点 cur通过 map.get(cur) 获取其对应的新节点然后利用 map.get(cur.next) 和 map.get(cur.random) 直接获取新节点的 next 与 random 指向的目标。由于 HashMap 的 get 方法在键为 null 时返回 null恰好天然处理了 next 或 random 为空的情况无需额外判断。这种分步策略的优势在于逻辑清晰且避免了重复查找或临时标记。空间上使用了 O(n) 的哈希表存储映射关系时间上两次线性遍历均为 O(n)总体 O(n)。相比在原链表节点间插入新节点再拆分的原地做法该方法以空间换取了代码的可读性与实现的简洁性更易于理解和维护。代码实现class Solution { public Node copyRandomList(Node head) { if (head null) return null; // 第一次遍历创建新节点并建立原节点 - 新节点的映射 MapNode, Node map new HashMap(); Node cur head; while (cur ! null) { map.put(cur, new Node(cur.val)); cur cur.next; } // 第二次遍历设置 next 和 random 指针 cur head; while (cur ! null) { Node newNode map.get(cur); newNode.next map.get(cur.next); // 可能为 nullmap.get(null) 返回 null newNode.random map.get(cur.random); // 同理 cur cur.next; } return map.get(head); } }时间复杂度On空间复杂度On4.排序链表思路解析本解法采用自底向上的迭代归并排序核心目标是在保证 O(n log n) 时间复杂度的前提下将空间复杂度严格控制在 O(1)。整体逻辑由主排序流程驱动并通过切割与合并两个辅助操作协同完成。算法首先遍历链表获取总长度作为控制合并轮次的终止条件。随后引入虚拟头节点指向原链表头以此统一每轮合并后的拼接操作消除对头节点的特殊判断。外层循环以步长从 1 开始逐轮倍增当步长达到或超过链表总长度时终止此时整个链表已有序。每一轮内部通过前驱指针与当前指针的配合依次处理所有相邻的子链表对先从当前位置切出指定步长的左子链表并获得右子链表起点再从该起点切出同等长度的右子链表并获得下一对的起始位置接着将左右两部分合并后接回主链表最后将前驱指针移至已合并段的末尾为下一次拼接做准备。切割操作被封装为独立函数其职责是从给定头节点出发截取最多指定数量的节点并返回剩余部分的起始位置。实现时向后移动相应步数若中途遇到空节点则提前终止随后断开当前节点的后续链接并返回原后续指针。这一设计使得不足指定长度的边界情况无需额外处理切割与定位一步完成。合并操作同样独立封装采用经典的双指针归并策略。通过局部虚拟头节点构建结果链表比较两链表当前节点值并将较小者接入尾部直至一方耗尽后直接拼接另一方剩余部分。该函数不依赖任何外部状态每次调用产生的局部变量在返回后自动释放不会累积额外空间开销。代码实现class Solution { public ListNode sortList(ListNode head) { if (head null || head.next null) return head; // 1. 统计链表长度 int len 0; for (ListNode cur head; cur ! null; cur cur.next) len; ListNode dummy new ListNode(0, head); // 2. 按步长 step 1, 2, 4, ... 逐轮合并 for (int step 1; step len; step 1) { ListNode prev dummy; ListNode curr dummy.next; while (curr ! null) { // 切出左半部分最多 step 个节点 ListNode left curr; ListNode right split(left, step); // 切出右半部分最多 step 个节点并返回下一段的起始位置 curr split(right, step); // 合并左右两部分并接回主链表 prev.next merge(left, right); // 移动 prev 到已合并段的末尾 while (prev.next ! null) prev prev.next; } } return dummy.next; } /** * 从 head 开始切出最多 n 个节点返回第 n1 个节点即下一段起点 * 同时将切出的子链表尾部 next 置空 */ private ListNode split(ListNode head, int n) { for (int i 1; head ! null i n; i) { head head.next; } if (head null) return null; ListNode next head.next; head.next null; // 断开 return next; } /** * 合并两个有序链表返回新头 */ private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode tail dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { tail.next l1; l1 l1.next; } else { tail.next l2; l2 l2.next; } tail tail.next; } tail.next (l1 ! null) ? l1 : l2; return dummy.next; } }时间复杂度Onlogn空间复杂度On5.合并 K 个升序链表思路解析面对 K 个有序链表的合并问题最直接的暴力做法是反复扫描所有链表头找最小值但每轮扫描耗时 O(K)总代价 O(NK) 显然不够高效。既然每次只需要当前全局最小自然联想到用最小堆来维护这个动态候选集堆中始终存放每条链表尚未处理的头节点取堆顶即得全局最小取出后若该链表还有后继便将后继补入堆中继续参与竞争。这样每次操作仅 O(log K)N 个节点总计 O(N log K)且堆的大小恒为 K空间 O(K)。基于这一思路代码实现分为三步。第一步是初始化创建以节点值为序的最小堆遍历输入数组将所有非空头节点入堆同时设立虚拟头节点作为结果链表的构建锚点。第二步是主循环只要堆非空就弹出堆顶节点接入结果链表尾部并检查其后继是否存在存在则入堆这一步将取最小与补后继合并在同一轮迭代中完成保证堆内始终是各链表当前的有效候选。第三步是返回虚拟头的下一个节点作为真正的结果头。代码实现public class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueueListNode pq new PriorityQueue((l1,l2)-(l1.val - l2.val)); for(ListNode l : lists){ if(l ! null) pq.add(l); } ListNode v new ListNode(0); ListNode pre v; while(!pq.isEmpty()){ ListNode cur pq.poll(); if(cur.next ! null) pq.add(cur.next); pre.next cur; pre pre.next; } return v.next; } }时间复杂度Onlogk空间复杂度Ok6. LRU 缓存思路解析设计 LRU 缓存的核心挑战在于同时满足两个操作均为 O(1)按 key 快速查找以及按访问时间顺序快速调整节点位置。哈希表天然支持 O(1) 查找但无法维护顺序链表能维护顺序但查找需线性扫描。因此将两者结合哈希表以 key 为键、节点引用为值实现即时定位双向链表按访问新旧排列节点最近使用的靠近尾部最久未使用的靠近头部插入、删除、移动均只需修改相邻指针无需遍历。为进一步消除边界判断引入虚拟头尾节点。它们不存储有效数据仅作为链表的固定锚点使得在尾部添加删除指定节点获取头部真实节点等操作无需区分空链表或单节点等特殊情况代码逻辑统一且不易出错。基于这一数据结构组合get 操作的流程是先通过哈希表查找 key 对应的节点若不存在直接返回 -1若存在则将该节点从当前位置摘除并重新接到链表尾部标记为最近使用再返回其 value。put 操作则分两种情况若 key 已存在更新节点值并将其移至尾部若 key 不存在需先检查容量是否已满满时则删除链表头部即 head.next所指向的真实节点同步从哈希表中移除对应条目并减少计数然后创建新节点加入尾部、写入哈希表并增加计数。整个过程中哈希表与链表的状态始终保持一致任何一方的变更都伴随另一方的同步更新确保查找与顺序维护的正确性。代码实现class LRUCache { class Node { int key, value; Node prev, next; Node(int k, int v) { key k; value v; } } private MapInteger, Node cache; private Node head, tail; private int capacity; private int size; public LRUCache(int capacity) { this.capacity capacity; this.size 0; cache new HashMap(); // 虚拟头尾节点简化边界操作 head new Node(0, 0); tail new Node(0, 0); head.next tail; tail.prev head; } private void addToTail(Node node) { node.prev tail.prev; node.next tail; tail.prev.next node; tail.prev node; } private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToTail(Node node) { removeNode(node); addToTail(node); } public int get(int key) { Node node cache.get(key); if (node null) return -1; moveToTail(node); // 更新为最近使用 return node.value; } public void put(int key, int value) { Node existing cache.get(key); if (existing ! null) { existing.value value; // 更新值 moveToTail(existing); } else { if (size capacity) { // 删除最久未使用的节点head.next Node lru head.next; cache.remove(lru.key); removeNode(lru); size--; } Node newNode new Node(key, value); cache.put(key, newNode); addToTail(newNode); size; } } }