手撕hot100之链表！看完这篇就AC~（六）

1 题目23. 合并 K 个升序链表给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。示例 1输入lists [[1,4,5],[1,3,4],[2,6]]输出[1,1,2,3,4,4,5,6]解释链表数组如下 [ 1-4-5, 1-3-4, 2-6 ] 将它们合并到一个有序链表中得到。 1-1-2-3-4-4-5-6示例 2输入lists []输出[]示例 3输入lists [[]]输出[]提示k lists.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i]按升序排列lists[i].length的总和不超过10^42 代码实现c/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { private: ListNode* merge(vectorListNode*list , int left , int right ){ if (left right) return list[left]; if (left right) return nullptr ; int mid left (right - left) / 2 ; ListNode* leftList merge(list,left ,mid); ListNode* rightList merge(list, mid 1 , right); return mergeTwoLists(leftList ,rightList); } ListNode* mergeTwoLists(ListNode* l1 , ListNode* l2 ){ ListNode* dummy new ListNode(0); ListNode* cur dummy ; while (l1 ! nullptr l2 ! nullptr){ if (l1 - val l2 - val){ cur - next l1 ; l1 l1 - next ; }else{ cur - next l2 ; l2 l2 - next ; } cur cur - next ; } cur - next l1 ! nullptr ? l1 : l2 ; return dummy - next ; } public: ListNode* mergeKLists(vectorListNode* lists) { return merge(lists, 0, lists.size() - 1); } };js/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } */ /** * param {ListNode[]} lists * return {ListNode} */ var mergeKLists function(lists) { function merge(l,r){ if (l r ) return lists[l] ; if (l r) return null ; let mid Math.floor((l r) / 2 ); let left merge(l, mid); let right merge(mid 1 , r); return mergeTwo (left ,right); } return merge(0,lists.length - 1 ); }; function mergeTwo (l1,l2){ let dummy new ListNode(0); let cur dummy ; while(l1 l2 ){ if (l1.val l2.val){ cur.next l1; l1 l1.next ; } else{ cur.next l2 ; l2 l2.next ; } cur cur.next; } cur.next l1 || l2 ; return dummy.next ; }思考我想到的就是两个两个合在一起类似于js里面的柯里化。毫无头绪呀...题解用分治把链表数组分成左右两半递归分别合并左半、右半最后把合并好的左链表 和 合并好的右链表做两链表合并时间复杂度 O (N logk)和小根堆一样最优代码极简超好写第一步合并两个有序链表必考工具函数// 合并两个升序链表 function mergeTwo(l1, l2) { let dummy new ListNode(); let cur dummy; while (l1 l2) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } cur.next l1 || l2; return dummy.next; }第二步完整版/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } */ /** * param {ListNode[]} lists * return {ListNode} */ var mergeKLists function(lists) { // 分治递归合并 [l, r] 区间的链表 function merge(l, r) { // 边界左右相等直接返回当前链表 if (l r) return lists[l]; // 越界返回空 if (l r) return null; // 中点二分 let mid Math.floor((l r) / 2); // 递归合并左半、右半 let left merge(l, mid); let right merge(mid 1, r); // 合并左右结果 return mergeTwo(left, right); } return merge(0, lists.length - 1); }; // 工具函数合并两个有序链表 function mergeTwo(l1, l2) { let dummy new ListNode(); let cur dummy; while (l1 l2) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } cur.next l1 || l2; return dummy.next; }1. 口述思路我采用分治归并的思路把链表数组从中间分成左右两部分递归分别合并左边所有链表、右边所有链表最后把合并完的两条有序链表再合并一次就能得到最终结果。时间复杂度 O (N logk)空间是递归栈效率最优也不用手动实现堆。2. 为什么面试不写最小堆JS 没有原生堆手写堆代码巨长、容易写错、超时分治代码短、逻辑清晰、递归模板固定默写零压力复杂度和堆完全一样面试官完全认可3. 思路写死mergeTwo合并两链表写递归merge(l, r)lr 返回当前链表算 mid递归左、递归右return mergeTwo (左右)主函数调用merge(0, len-1)二分递归拆两半左右各自往里算最后两两合一遍dummy 节点永不变。3 题目138. 随机链表的复制给你一个长度为n的链表每个节点包含一个额外增加的随机指针random该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。 深拷贝应该正好由n个全新节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。例如如果原链表中有X和Y两个节点其中X.random -- Y。那么在复制链表中对应的两个节点x和y同样有x.random -- y。返回复制链表的头节点。用一个由n个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示val一个表示Node.val的整数。random_index随机指针指向的节点索引范围从0到n-1如果不指向任何节点则为null。你的代码只接受原链表的头节点head作为传入参数。示例 1输入head [[7,null],[13,0],[11,4],[10,2],[1,0]]输出[[7,null],[13,0],[11,4],[10,2],[1,0]]示例 2输入head [[1,1],[2,1]]输出[[1,1],[2,1]]示例 3输入head [[3,null],[3,0],[3,null]]输出[[3,null],[3,0],[3,null]]提示0 n 1000-104 Node.val 104Node.random为null或指向链表中的节点。4 代码实现c/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if(!head) return nullptr ; unordered_map Node* , Node* map ; Node* cur head ; while (cur){ map[cur] new Node(cur - val ); cur cur - next ; } cur head ; while(cur){ Node* newNode map[cur]; newNode - next map[cur - next]; newNode - random map[cur - random]; cur cur - next ; } return map[head]; } };#include unordered_map using namespace std; class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; // ️ 核心旧节点 - 新节点 的映射表 unordered_mapNode*, Node* map; // // 第一步先创建所有新节点存入 map // Node* cur head; while (cur) { map[cur] new Node(cur-val); // 旧cur → 新节点 cur cur-next; } // // 第二步给新节点连 next 和 random // cur head; while (cur) { // 取出当前旧节点对应的新节点 Node* newNode map[cur]; // 新节点next 旧节点next对应的新节点 newNode-next map[cur-next]; // 新节点random 旧节点random对应的新节点 newNode-random map[cur-random]; cur cur-next; } // 返回新链表的头 return map[head]; } };js/** * // Definition for a _Node. * function _Node(val, next, random) { * this.val val; * this.next next; * this.random random; * }; */ /** * param {_Node} head * return {_Node} */ var copyRandomList function(head) { if (!head) return null ; let map new Map(); let cur head ; while (cur){ map.set(cur , new Node(cur.val)); cur cur.next ; } cur head ; while (cur){ map.get(cur).next map.get(cur.next) || null ; map.get(cur).random map.get(cur.random) || null ; cur cur.next ; } return map.get(head); };思考意思就是自己再去实现一个链表深拷贝包含之前的指针指向关系。用map维护一个表每一个节点知道自己的val next random 指针。题解第一轮Map 只做「旧节点 → 新节点 绑定登记」第二轮利用这个绑定通过旧节点的 next /random 找到对应的新节点把新链表的指针全部接上一、题目到底在考什么给你一个带 random 随机指针的链表让你深拷贝一份一模一样的新链表。新节点必须是全新创建的next 和 random 都要指向新节点不能指向原来的旧节点你的思路完全正确用 Map 存 旧节点 → 新节点 的映射靠这个映射复制指针关系二、最简单面试写法哈希表Map法核心思路第一遍遍历创建所有新节点用Map存旧节点 → 新节点第二遍遍历复制next和random指针新节点.next map.get (旧节点.next)新节点.random map.get (旧节点.random)返回map.get (head) 就是新链表头/** * // Definition for a Node. * function Node(val, next, random) { * this.val val; * this.next next; * this.random random; * }; */ /** * param {Node} head * return {Node} */ var copyRandomList function(head) { if (!head) return null; let map new Map(); let cur head; // 第1步复制所有节点存进 map 旧 - 新 while (cur) { map.set(cur, new Node(cur.val)); cur cur.next; } // 第2步复制 next 和 random 指针 cur head; while (cur) { map.get(cur).next map.get(cur.next) || null; map.get(cur).random map.get(cur.random) || null; cur cur.next; } // 第3步返回复制后的头节点 return map.get(head); };三、面试现场怎么说我使用 ** 哈希表Map** 来实现深拷贝第一遍遍历原链表创建所有新节点用 Map 保存旧节点到新节点的映射。第二遍遍历通过映射关系给新节点设置 next 和 random 指针。这样就能保证所有指针都指向新创建的节点完成深拷贝。时间 O (n)空间 O (n)逻辑清晰代码好写不易错。四、代码逐行超简单解释// 1. 旧节点对应的新节点全部先建好 map.set(cur, new Node(cur.val)); // 2. 新节点的 next 旧节点next 对应的新节点 map.get(cur).next map.get(cur.next) // 3. 新节点的 random 旧节点random 对应的新节点 map.get(cur).random map.get(cur.random)先复制节点存 map再复制指针。一遍建节点map 来关联。二遍连指针next random。返回新头结点深拷贝完成。5 小结一、23 合并 K 个升序链表1. 思路模板先写合并两个有序链表工具函数dummy 必用分治递归对半拆递归合左、递归合右左右结果再调用两链表合并2. 面试口述分治二分递归合并左右区间最后合并两条有序链表复杂度 O (Nlogk)。3. 口诀二分拆两半递归算左右两两再合并dummy 不走丢。4. 代码骨架默写版工具mergeTwo(l1,l2)双指针 虚拟头递归merge(l,r)lr 返回当前链表lr 返回空求 mid递归左、递归右return mergeTwo (左右)主函数merge(0,len-1)二、138 随机链表复制1. 思路模板判空用Map 旧节点→新节点第一轮遍历只建新节点、存映射第二轮遍历给新节点挂 next、random查表赋值返回原头对应的新头2. 面试口述哈希存旧节点到新节点映射第一遍建所有新节点第二遍补 next 和 random 指针完成深拷贝。3. 口诀一遍建节点二遍连指针Map 做映射拷贝不翻车。4. 代码骨架默写版判空直接返回开 unordered_map / Map第一次循环map[cur] new Node(val)第二次循环取新节点新节点 next map [旧 next]新节点 random map [旧 random]返回map[head]三、通用极简套路链表合并dummy 分治 两链表合并随机深拷贝两轮遍历 Map 新旧映射遇到多有序合并 → 直接上分治遇到随机 / 复杂指针拷贝 → 直接上 Map 两轮遍历