目录138. 随机链表的复制题目链接题目简介解题思路满分代码极简注释版148. 排序链表题目链接题目简介解题思路满分代码规范命名 超强注释138. 随机链表的复制题目链接138. 随机链表的复制 - 力扣LeetCode题目简介给你一个长度为n的随机链表每个节点包含一个额外的随机指针该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。解题思路普通链表复制只需处理next指针而本题难点在于随机指针random的指向无法一次性确定。我们用哈希表完美解决核心分两步遍历逻辑简单无坑第一遍遍历不处理指针关系仅克隆所有节点用HashMap存储原节点 → 新节点的映射关系第二遍遍历根据哈希表直接为新节点赋值next和random指针一步到位。满分代码极简注释版java运行/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val val; this.next null; this.random null; } } */ class Solution { public Node copyRandomList(Node head) { // 边界判断空链表直接返回 if(head null){ return null; } // 哈希表key 原节点value 克隆的新节点 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){ // 复制 next 指针 if(cur.next ! null){ map.get(cur).next map.get(cur.next); } // 复制 random 指针 if(cur.random ! null){ map.get(cur).random map.get(cur.random); } cur cur.next; } // 返回克隆链表的头节点 return map.get(head); } }148. 排序链表题目链接148. 排序链表 - 力扣LeetCode题目简介给你链表的头结点head请将其按升序排列并返回排序后的链表要求时间复杂度 O(nlogn)。解题思路链表排序最优解归并排序递归版链表不支持随机访问快排 / 堆排都不适用而归并排序天然适配链表结构核心分两大步骤分割链表快慢指针找中点将链表从中间切断递归分割至每个子链表只有 1 个节点天然有序合并有序链表双指针合并两个有序子链表最终得到完整有序链表。满分代码规范命名 超强注释java运行/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode sortList(ListNode head) { // 递归终止条件空节点 或 单个节点无需排序 if(head null || head.next null){ return head; } // 快慢指针寻找链表中点偶数节点找左中点 ListNode fast head, slow head; while(fast.next ! null fast.next.next ! null){ slow slow.next; fast fast.next.next; } // 从中点切断链表分割为左右两个子链表 ListNode mid slow.next; slow.next null; // 递归排序左右子链表 ListNode left sortList(head); ListNode right sortList(mid); // 合并两个有序链表虚拟头节点简化操作 ListNode dummy new ListNode(Integer.MIN_VALUE); ListNode cur dummy; while(left ! null right ! null){ if(left.val right.val){ cur.next left; left left.next; }else{ cur.next right; right right.next; } cur cur.next; } // 拼接剩余未遍历完的节点 cur.next left ! null ? left : right; // 返回排序后的链表头 return dummy.next; } }