企业官网建设流程全解析

本章包括的题目有：

24. 两两交换链表中的节点 - 力扣（LeetCode）

25. K 个一组翻转链表 - 力扣（LeetCode）

138. 随机链表的复制 - 力扣（LeetCode）

148. 排序链表 - 力扣（LeetCode）

23. 合并 K 个升序链表 - 力扣（LeetCode）

146. LRU 缓存 - 力扣（LeetCode）

1.两两交换链表中的节点

思路解析：

这道题的难点在于两两交换时指针容易丢失，尤其是头节点也会参与交换，直接操作很容易出错。代码采用了一个比较稳妥的策略：先把每一对中靠前的节点按顺序存进数组，把链表的动态结构"拍平"成静态的索引关系，后续所有指针修改都基于数组下标进行，避免了边遍历边改指针带来的混乱。

具体来说，第一轮遍历只收集每对的起始节点，第二轮遍历则根据数组中的位置关系统一处理交换和拼接：当前对的第二个节点指向第一个节点完成内部交换，而第一个节点的 next 则根据下一对是否存在来决定接谁——如果还有下一对，就接下一对的第二个节点（即arr[i+1].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; ArrayList<ListNode> 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(i+1).next != null) arr.get(i).next = arr.get(i+1).next; else arr.get(i).next = arr.get(i+1); }else arr.get(i).next = null; } } return nex; } }

时间复杂度O（n）

空间复杂度O（n）

2.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; } }

时间复杂度O（n）

空间复杂度O（1）

3.随机链表的复制

思路解析：

这道题的难点在于 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; // 第一次遍历：创建新节点，并建立原节点 -> 新节点的映射 Map<Node, 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); // 可能为 null，map.get(null) 返回 null newNode.random = map.get(cur.random); // 同理 cur = cur.next; } return map.get(head); } }

时间复杂度O（n）

空间复杂度O（n）

4.排序链表

思路解析：

本解法采用自底向上的迭代归并排序，核心目标是在保证 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 个节点，返回第 n+1 个节点（即下一段起点） * 同时将切出的子链表尾部 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; } }

时间复杂度O（nlogn）

空间复杂度O（n）

5.合并 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) { PriorityQueue<ListNode> 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; } }

时间复杂度O（nlogk）

空间复杂度O（k）

6. 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 Map<Integer, 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++; } } }