Hot100（开刷） 之 环形链表（II）-- 随机链表的复制 -- 翻转二叉树

三十二、环形链表II _ 检测环的入口点1.一句话描述思路用哈希集合记录所有访问过的节点遍历链表时第一个重复遇到的节点即为环的入口若遍历结束无重复则无环。//java版本 public ListNode detectCycle(ListNode head) { // 创建一个指针 pos初始指向链表头节点用于遍历链表 ListNode pos head; // 创建一个 HashSet用于存储已经访问过的节点对象基于节点引用 SetListNode visited new HashSetListNode(); // 当 pos 不为 null 时继续遍历链表 while (pos ! null) { // 检查当前节点是否已经被访问过即是否在 set 中 if (visited.contains(pos)) { // 如果已经访问过说明当前节点就是环的入口节点因为第一次遇到重复节点 return pos; } else { // 否则将当前节点加入 visited 集合标记为已访问 visited.add(pos); } // 将指针移动到下一个节点继续遍历 pos pos.next; } // 如果遍历完整个链表pos 变为 null都没有遇到重复节点说明链表无环返回 null return null; }// Kotlin版本 fun detectCycle(head: ListNode?): ListNode? { // 创建一个指针 pos初始指向链表头节点用于遍历链表 var pos head // 创建一个 HashSet用于存储已经访问过的节点对象基于节点引用 val visited HashSetListNode() // 当 pos 不为 null 时继续遍历链表 while (pos ! null) { // 检查当前节点是否已经被访问过即是否在 set 中 if (visited.contains(pos)) { // 如果已经访问过说明当前节点就是环的入口节点因为第一次遇到重复节点 return pos } else { // 否则将当前节点加入 visited 集合标记为已访问 visited.add(pos) } // 将指针移动到下一个节点继续遍历 pos pos.next } // 如果遍历完整个链表pos 变为 null都没有遇到重复节点说明链表无环返回 null return null } }2.代码逻辑详解从链表头结点head开始用指针pos指向当前节点。创建一个HashSetListNode用于存储已经遍历过的节点引用。循环遍历链表直到pos为null表示到达链表尾部。对于每个节点检查它是否已经存在于集合中如果存在说明之前已经经过该节点这正是环的起始节点因为第一次重复遇到的节点就是环的入口直接返回该节点。如果不存在将该节点加入集合。移动指针到下一个节点继续循环。如果循环正常结束pos null说明链表中没有环返回null。3.关键点哈希集合的妙用利用集合的O(1)平均查找时间复杂度快速检测重复节点。环的入口判定第一个重复出现的节点一定是环的起始节点因为从head出发进入环后再次访问到的第一个环上节点就是入口。终止条件既要处理无环遇到null也要处理有环遇到已访问节点。节点比较这里比较的是节点对象引用内存地址而不是节点值因此不会因为值相同而误判。4.复杂度分析时间复杂度O(n)最坏情况下每个节点被访问一次集合的插入和查找操作平均为 O(1)因此总时间复杂度为 O(n)其中 n 为链表节点数。空间复杂度O(n)需要使用一个哈希集合来存储最多 n 个节点的引用因此额外空间与链表长度成正比。5.优缺点优点实现简单直观容易理解和编写。通用性强不要求修改链表结构或节点值适用于只读场景。能准确返回环的入口节点而不仅仅是判断是否有环。缺点空间开销大需要 O(n) 的额外存储空间当链表很长时内存占用较高。无法处理无法使用哈希的场景如内存极度受限的环境。相比双指针Floyd 判圈算法效率较低后者只需要 O(1) 额外空间。三十三、随机链表的复制1.一句话算法流程描述分三步①在原链表每个节点后插入其副本②根据原节点的 random 指针设置副本的 random③拆开混合链表恢复原链表并提取新链表。//Java版本 public Node copyRandomList(Node head) { // 边界条件如果原链表为空直接返回 null if (head null) { return null; } // 第一步在原链表的每个节点后面插入一个自己的副本 // 例如原链表 A - B - C // 插入后A - A - B - B - C - C for (Node node head; node ! null; node node.next.next) { // 创建当前节点的新副本值与原节点相同 Node nodeNew new Node(node.val); // 新副本的 next 指向原节点的下一个节点 nodeNew.next node.next; // 原节点的 next 指向新副本完成插入 node.next nodeNew; } // 第二步设置新节点的 random 指针 // 此时链表结构为原节点 - 新节点 - 原节点 - 新节点 ... // 原节点 node 的 random 指向某个原节点那么 node.next新节点的 random 应该指向 node.random.next那个原节点对应的新节点 for (Node node head; node ! null; node node.next.next) { // 获取当前原节点对应的新节点 Node nodeNew node.next; // 如果原节点的 random 不为空则新节点的 random 指向原节点的 random 所指节点的下一个节点即对应的新节点 // 否则新节点的 random 设为 null nodeNew.random (node.random ! null) ? node.random.next : null; } // 第三步将原链表和新链表拆分开 // 新链表的头节点就是原链表头节点的下一个节点 Node headNew head.next; // 遍历整个混合链表分离出原链表和新链表 for (Node node head; node ! null; node node.next) { // nodeNew 是当前原节点对应的新节点 Node nodeNew node.next; // 恢复原节点的 next 指针跳过新节点指向原来的下一个原节点即 nodeNew.next node.next node.next.next; // 恢复新节点的 next 指针如果 nodeNew 后面还有新节点则指向那个新节点否则为 null nodeNew.next (nodeNew.next ! null) ? nodeNew.next.next : null; } // 返回新链表的头节点 return headNew; } }// Kotlin fun copyRandomList(head: Node?): Node? { // 边界条件空链表直接返回 null if (head null) return null // 第一步插入副本节点 // 原链表A - B - C // 插入后A - A - B - B - C - C var node: Node? head while (node ! null) { val newNode Node(node.val) // 创建副本 newNode.next node.next // 副本的 next 指向原节点的下一个 node.next newNode // 原节点的 next 指向副本 node newNode.next // 跳两步继续处理下一个原节点 } // 第二步设置副本节点的 random // 此时结构原节点 - 副本节点 - 原节点 - 副本节点 ... // 原节点 node 的 random 指向某原节点 target // 则 node.next副本节点的 random 应指向 target?.next对应的副本节点 node head while (node ! null) { val newNode node.next // 当前原节点对应的副本节点 // 原节点的 random 可能为 null需处理空安全 newNode?.random node.random?.next node newNode?.next // 跳两步到下一个原节点 } // 第三步拆分原链表和新链表 val newHead head.next // 新链表的头节点 var cur: Node? head while (cur ! null) { val copy cur.next // 副本节点 // 恢复原链表的 next原节点指向原节点的下一个原节点跳过副本 cur.next copy?.next // 恢复副本链表的 next副本节点指向下一个副本节点如果存在 copy?.next copy.next?.next cur cur.next // 移动到下一个原节点 } return newHead }2.代码逻辑详解分步说明第一步插入副本节点遍历原链表在每个节点node后面插入一个值相同的新节点newNode。newNode.next node.next让副本指向原节点的下一个节点。node.next newNode让原节点指向副本。然后将指针移动到newNode.next即原链表的下一个原节点继续处理。效果A → A → B → B → C → C → null第二步设置副本的 random 指针再次遍历混合链表每次取一对(原节点, 副本节点)。原节点node的random可能指向某个原节点或null。因为副本节点node.next正好紧跟在原节点后面且原节点的random指向的目标原节点target的副本正好是target.next。所以设置node.next.random node.random?.next若node.random为null则副本的random也为null。第三步拆分两个链表新链表的头节点已确定为head.next。再次遍历混合链表恢复原链表的next指针让它跳过副本节点指向下一个原节点。同时恢复副本链表的next指针让副本节点指向下一个副本节点若存在。遍历结束后原链表恢复原状新链表独立存在。3.关键点三步法插入 → 设置 random → 拆分缺一不可。空间 O(1) 原地修改不使用额外哈希表只在原链表上操作。random 指针的映射关系利用原节点.random与原节点.random.next的对应关系无需额外存储映射。指针移动步长插入时每次跳两步设置 random 时也跳两步拆分时每次跳一步。空指针处理需注意node.random可能为nullKotlin 中用?.安全调用。4.复杂度分析时间复杂度O(n)链表被完整遍历三次插入、设 random、拆分每次遍历都是线性时间。空间复杂度O(1)不计输出链表除了返回的新链表节点外只使用了常数个临时指针变量。新链表节点本身是题目要求的输出不算额外空间。5.优缺点优点空间效率极高O(1) 额外空间优于哈希表法O(n)。不依赖哈希函数适用于所有环境。一次遍历即可建立 random 映射逻辑清晰。缺点实现稍复杂需要谨慎处理指针移动和空值容易出错。修改了原链表结构虽然最后恢复了在多线程或只读场景下不适用。需要三次遍历常数时间略高于哈希表法但渐进复杂度相同。三十四、翻转二叉树1.一句话算法流程描述使用队列按层遍历二叉树对每个出队节点交换其左右子节点并将非空子节点入队直到队列为空。//Java版本 public TreeNode invertTree(TreeNode root) { // 基础情况如果当前节点为空直接返回 null if (root null) { return null; } // 创建一个队列使用 LinkedList 实现用于存储待处理的节点 // 队列遵循先进先出原则保证按层处理节点层序遍历 LinkedListTreeNode queue new LinkedListTreeNode(); // 将根节点加入队列开始遍历 queue.add(root); // 循环处理队列中的所有节点直到队列为空 while (!queue.isEmpty()) { // 从队列头部取出一个节点当前待处理的节点 TreeNode tmp queue.poll(); // 交换该节点的左右子节点 TreeNode left tmp.left; // 暂存左子节点 tmp.left tmp.right; // 将右子节点赋值给左子节点 tmp.right left; // 将原左子节点赋值给右子节点 // 如果当前节点的左子节点不为空则将其加入队列以便后续处理其子节点 if (tmp.left ! null) { queue.add(tmp.left); } // 如果当前节点的右子节点不为空则将其加入队列以便后续处理其子节点 if (tmp.right ! null) { queue.add(tmp.right); } } // 返回翻转后的根节点原根节点位置不变但其左右子树已交换 return root; }//Kotlin版本 fun invertTree(root: TreeNode?): TreeNode? { // 边界条件空树直接返回 null if (root null) return null // 使用队列进行层序遍历FIFO val queue: ArrayDequeTreeNode ArrayDeque() queue.addLast(root) // 根节点入队 while (queue.isNotEmpty()) { // 取出队首节点 val current queue.removeFirst() // 交换当前节点的左右子节点 val temp current.left current.left current.right current.right temp // 如果左子节点不为空入队以便后续处理其子节点 current.left?.let { queue.addLast(it) } // 如果右子节点不为空入队 current.right?.let { queue.addLast(it) } } // 返回原根节点树结构已被原地翻转 return root } }2.代码逻辑详解分步说明处理空树如果root null直接返回null无需任何操作。初始化队列使用双端队列ArrayDeque作为队列将根节点加入队列。循环处理队列只要队列不为空从队首取出一个节点current。交换current的左右子节点借助临时变量temp存储left然后left rightright temp。检查交换后的左子节点原来的右子节点是否为null若不为空则入队。检查交换后的右子节点原来的左子节点是否为null若不为空则入队。循环结束所有节点处理完毕后返回根节点。原二叉树的每个节点都已交换左右子树实现了整棵树的翻转。3.关键点层序遍历广度优先利用队列按层处理节点确保每个节点都被访问一次。原地翻转直接修改原二叉树的节点引用不创建新树空间效率高。空节点处理在入队前检查子节点是否为空避免将null加入队列。交换操作使用临时变量或 Kotlin 的also/let均可本质是交换两个引用。适用性此方法对任何二叉树都有效包括完全二叉树、退化链表等。4.复杂度分析时间复杂度O(n)每个节点恰好入队一次、出队一次交换操作是 O(1)总操作次数与节点数 n 成正比。空间复杂度O(n)最坏情况下满二叉树队列中最多同时存储约 n/2 个节点最后一层因此额外空间为 O(n)。注若考虑递归解法递归栈深度 O(h) 更优但此处为队列实现。5.优缺点优点直观易懂层序遍历思想简单交换左右子树的逻辑清晰。避免递归栈溢出对于深度极大的树如链状树不会像递归解法那样可能导致栈溢出。原地修改不占用额外树节点空间仅使用队列存储指针。缺点空间复杂度较高最坏情况下需要 O(n) 的队列空间而递归解法DFS只需要 O(h) 的栈空间h 为树高。对于满二叉树两者都是 O(n)但常数因子队列稍大。代码略冗长相比递归解法几行代码队列实现需要显式管理队列。需要额外数据结构依赖队列容器在某些受限环境中可能不可用。